A fast algorithm for streaming betweenness centrality

Oded Green, Robert McColl, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

83 Scopus citations

Abstract

Analysis of social networks is challenging due to the rapid changes of its members and their relationships. For many cases it impractical to recompute the metric of interest, therefore, streaming algorithms are used to reduce the total runtime following modifications to the graph. Centrality is often used for determining the relative importance of a vertex or edge in a graph. The vertex Between ness Centrality is the fraction of shortest paths going through a vertex among all shortest paths in the graph. Vertices with a high between ness centrality are usually key players in a social network or a bottleneck in a communication network. Evaluating the between ness centrality for a graph G=(V, E) is computationally demanding and the best known algorithm for unweighted graphs has an upper bound time complexity of O(V2+VE). Consequently, it is desirable to find a way to avoid a full re-computation of between ness centrality when a new edge is inserted into the graph. In this work, we give a novel algorithm that reduces computation for the insertion of an edge into the graph. This is the first algorithm for the computation of between ness centrality in a streaming graph. While the upper bound time complexity of the new algorithm is the same as the upper bound for the static graph algorithm, we show significant speedups for both synthetic and real graphs. For synthetic graphs the speedup varies depending on the type of graph and the graph size. For synthetic graphs with 16384 vertices the average speedup is between 100X-400X. For five different real world collaboration networks the average speedup per graph is in range of 36X-148X.

Original languageEnglish (US)
Title of host publicationProceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012
Pages11-20
Number of pages10
DOIs
StatePublished - 2012
Externally publishedYes
Event2012 ASE/IEEE International Conference on Social Computing, SocialCom 2012 and the 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust, PASSAT 2012 - Amsterdam, Netherlands
Duration: Sep 3 2012Sep 5 2012

Publication series

NameProceedings - 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing, SocialCom/PASSAT 2012

Conference

Conference2012 ASE/IEEE International Conference on Social Computing, SocialCom 2012 and the 2012 ASE/IEEE International Conference on Privacy, Security, Risk and Trust, PASSAT 2012
Country/TerritoryNetherlands
CityAmsterdam
Period9/3/129/5/12

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality

Keywords

  • graph algorithms
  • social networks

Fingerprint

Dive into the research topics of 'A fast algorithm for streaming betweenness centrality'. Together they form a unique fingerprint.

Cite this