document: HyperANF : approximating the neighborhood function of very large graphs on a budget The neighborhood function NG ( t ) of a graph G gives , for each t ∈ N , the number of pairs of nodes x , y such that y is reachable from x in less that t hops . The neighborhood function provides a wealth of information about the graph ( 10 ) ( e.g. , it easily allows one to compute its diameter ) , but it is very expensive to compute it exactly . Recently , the ANF algorithm ( 10 ) ( approximate neighborhood 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 ( 5 ) and combines them efficiently through broadword programming ( 8 ) ; our implementation uses talk decomposition to exploit multi-core parallelism . With HyperANF , for the first time we can compute in a few hours the neighborhood 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 distances 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O