Arge, Lars4; Goodrich, Michael T.3; Walderveen, Freek van4
1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University3 Dept. of Computer Science School of Info. & Comp. Sci. University of Californ4 Department of Computer Science, Science and Technology, Aarhus University
Betweenness centrality is one of the most well-known measures of the importance of nodes in a social-network graph. In this paper we describe the first known external-memory and cache-oblivious algorithms for computing betweenness centrality. We present four different external-memory algorithms exhibiting various tradeoffs with respect to performance. Two of the algorithms are cache-oblivious. We describe general algorithms for networks with weighted and unweighted edges and a specialized algorithm for networks with small diameters, as is common in social networks exhibiting the “small worlds” phenomenon.
Proceedings, 2013 Ieee International Conference on Big Data, 2013, p. 368-375