g-Off.net | Geoffrey Foster

Parallel Betweenness Centrality Measurement in Large-Scale Social Networks

Project Outline: The concept of Betweenness Centrality was first introduced by Freeman as a measure of the importance of a node (actor) in a network based upon how much traffic flows through them. For a given graph G = (V, E) that has n vertices, the betweenness centrality (CB(v)) is measured for a vertex, v by the following:

where σ_st is the number of shortest paths from s to t and σ_st(v) is the number of shortest paths from s to t that pass through the vertex v. Typical sequential betweenness centrality algorithms use a breadth-first-search which has a runtime of O(n + m), wheren = |V|, m = |E|, and thus an overall runtime of O(n(n + m)) since a breadth-first-search must be done for each vertex. For large scale networks this can be quite costly. In order to reduce the amount of time for these computations approximations can be performed. The aim of this project is to develop and test a parallel implementation for computing an approximated betweenness centrality on a real-world, large-scale social network data set.

Startup Paper(s):

1. Eunice E. Santos, Long Pan, Dustin Arendt, and Morgan Pittkin. "An Effective Anytime Anywhere Parallel Approach for Centrality Measurements in Social Network Analysis". 2006 IEEE International Conference on Systems, Man, and Cybernetics, pp 4693-4698, October 2006.
2. David A. Bader and Kamesh Madduri. "Parallel Algorithms for Evaluating Centrality Indices in Real-world Networks". Proceedings of the 2006 International Conference on Parallel Processing.

Deliverables:

Relevant References