Large-scale network analytics: diffusion-based computation of distances and geometric centralities

Given a large complex network, which of its nodes are more central? This question emerged in many contexts (e.g., sociology, psychology and computer science), and gave rise to a large range of proposed centrality measures. Providing a sufficiently general and mathematically sound classification of these measures is challenging: on one hand, it requires that one can suggest some simple, basic properties that a centrality measure should exhibit; on the other hand, it calls for innovative algorithms that allow an efficient computation of these measures on large real networks. HyperBall is a recently proposed tool that accesses the graph in a semi-streaming fashion and is at the same time able to compute the distance distribution and to approximate all geometric (i.e., distance-based) centralities. It uses a very small amount of core memory, thanks to the application of HyperLogLog counters, and exhibits high, guaranteed accuracy.