[Networkit] Request for Code Review: Effective Diameter and Hop Plot

Christian Staudt christian.staudt at kit.edu
Thu Aug 21 14:58:39 CEST 2014


Hi NetworKit developers,
student Marc Nemes is working on extensions for NetworKit and has implemented functions for effective diameter (exact and approximated) and hop plots. The code is in the branch „nemes“. Let’s test and review the code, paying attention to correctness and performance.

Here is his description of the new features:

> I've just completed the implementation of the effective diameter and the hop-plot.
> The effective diameter equals the number of edges needed on average to reach 90% of all other nodes. 
> The hop-plot is the fraction of connected nodes g(d) for each step range d.
> The computation uses bitmasks to store the reachable nodes for each node within the current distance, however, the length of the bitmasks is log2(n) so multiple nodes get mapped to the same bit.
> So the final algorithm is an approximation in O((n+m)d) which uses a bitwise or to merge a nodes bitmask with the bitmasks of all its neighbours and then estimates the number of reachable nodes within that distance based on this new bitmask.
> To get a more stable result, k different bitmasks are generated for each node and the average of all its bitmasks is taken.
> The core of the algorithm can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf
> More information about probabilistic counting can be found here: http://algo.inria.fr/flajolet/Publications/FlMa85.pdf
> 
> I guess there are some points that can be improved so I'd like to have some feedback on the current code.
> 
> 
> Regards
> Marc

Thank you
Christian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140821/95629a1e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140821/95629a1e/attachment.sig>


More information about the NetworKit mailing list