HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget

Details HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget

2010-11-25

arxiv.org/abs/1011.5599v2

Computer Science

Data Structures and Algorithms

Scientific paper

The neighbourhood function N(t) of a graph G gives, for each t, the number of pairs of nodes such that y is reachable from x in less that t hops. The neighbourhood function provides a wealth of information about the graph (e.g., it easily allows one to compute its diameter), but it is very expensive to compute it exactly. Recently, the ANF algorithm (approximate neighbourhood function) has been proposed with the purpose of approximating NG(t) on large graphs. We describe a breakthrough improvement over ANF in terms of speed and scalability. Our algorithm, called HyperANF, uses the new HyperLogLog counters and combines them efficiently through broadword programming; our implementation uses overdecomposition to exploit multi-core parallelism. With HyperANF, for the first time we can compute in a few hours the neighbourhood function of graphs with billions of nodes with a small error and good confidence using a standard workstation. Then, we turn to the study of the distribution of the shortest paths between reachable nodes (that can be efficiently approximated by means of HyperANF), and discover the surprising fact that its index of dispersion provides a clear-cut characterisation of proper social networks vs. web graphs. We thus propose the spid (Shortest-Paths Index of Dispersion) of a graph as a new, informative statistics that is able to discriminate between the above two types of graphs. We believe this is the first proposal of a significant new non-local structural index for complex networks whose computation is highly scalable.

Affiliated with

Also associated with

No associations

Rating

HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-587777