Lars Arge

Computing betweenness centrality in external memory

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Arge
  • Michael T. Goodrich, Dept. of Computer Science School of Info. & Comp. Sci. University of Californ, United States
  • Freek van Walderveen, Denmark
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.
Original languageEnglish
Title of host publicationProceedings, 2013 IEEE International Conference on Big Data
Number of pages8
PublisherIEEE
Publication year2013
Pages368 - 375
ISBN (print)978-1-4799-1292-6
DOIs
Publication statusPublished - 2013
EventInternational Conference on Big Data - Santa Clara, United States
Duration: 6 Oct 20139 Oct 2013

Conference

ConferenceInternational Conference on Big Data
LandUnited States
BySanta Clara
Periode06/10/201309/10/2013

See relations at Aarhus University Citationformats

ID: 68515050