Scaling up Network Centrality Computations
Alexander van der Grintena and Henning Meyerhenkeb
Department of Computer Science Humboldt-Universität zu Berlin Berlin, Germany
aavdgrinten@hu-berlin.de
bmeyerhenke@hu-berlin.de
ABSTRACT
Network science methodology is increasingly applied to a large variety of real-world phenomena. Thus, network data sets with millions or billions of edges are more and more common. To process and analyze such graphs, we need appropriate graph processing systems and fast algorithms. Many analysis algorithms have been pioneered, however, on small networks when speed was not the highest concern. Developing an analysis toolkit for largescale networks thus often requires faster variants, both from an algorithmic and an implementation perspective. In this paper we focus on computational aspects of vertex centrality measures. Such measures indicate the importance of a vertex based on the position of the vertex in the network. We describe several common measures as well as algorithms for computing them. The description has two foci: (i) our recent contributions to the field and (ii) possible future work, particularly regarding lower-level implementation.
Keywords: Algorithmic network analysis, centrality computations, shortest paths, linear systems
