Betweenness Centrality

Application Description

This benchmark computes the betweenness centrality of each node in a network, a metric that captures the importance of each individual node in the overall network structure. Betweenness centrality is a shortest path enumeration-based metric. Informally, it is defined as follows. Let \(G=(V,E)\) be a graph and let \(s,t\) be a fixed pair of graph nodes.The betweenness score of a node \(u\) is the percentage of shortest paths between \(s\) and \(t\) that include \(u\). The betweenness centrality of \(u\) is the sum of its betweenness scores for all possible pairs of \(s\) and \(t\) in the graph. The benchmark takes as input a directed graph and returns the betweenness centrality value of each node.

Algorithm

The parallel implementation is based on Brandes' algorithm [1]. Brandes' algorithm exploits the sparse nature of typical real-world graphs, and computes the betweenness centrality score for all vertices in the graph in \(O(VE + V^2 \log{V})\) time for weighted graphs, and \(O(VE)\) time for unweighted graphs. The current implementation deals only with unweighted graphs.

Formally, let \(G=(V,E)\) be a graph and let \(s,t\) be a fixed pair of graph nodes. Let \(\sigma_{st}\) be the number of shortest paths between \(s\) and \(t\), and let \(\sigma_{st}(v)\) be the number of those shortest paths that pass through \(v\). We define the dependency of a source vertex \(s\) on a vertex \(v\) as: \[ \delta_{s}(v) = \sum_{t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}} \] This dependency captures the importance of the node with respect to \(s\) and \(t\). The betweenness centrality of a vertex \(v\) is then expressed as: \[ BC(v) = \sum_{s \neq v \in V} \delta_{s}(v) \] The key insight is that the dependency of a node \(v\) satisfies the following recurrence: \[ \delta_{s}(v) = \sum_{w \colon v \in pred(s,w)} \frac{\sigma_{sv}}{\sigma_{sw}}(1 + \delta_{s}(w)) \] where \(pred(s,w)\) is the set of predecessors of \(w\) in the shortest paths from \(s\) to \(w\).

Using this insight Brandes' algorithm works as follows. Initially, \(V\) shortest-path computations are done, one for each \(s \in V\). In the case of unweighted graphs, these shortest path computations correspond to breadth-first search (BFS) explorations. The predecessor sets \(pred(s,v)\), and \(\sigma_{sv}\) values are computed during these shortest-path explorations. Next, for every possible source \(s\), using the information from the shortest paths tree and the DAG that is induced on the graph by the predecessor sets, we compute the dependencies \(\delta_{s}(v)\) for all other \(v \in V\). To compute the centrality value of a node \(v\), we finally compute the sum of all dependency values.

This algorithm has parallelism at multiple levels. Firstly, we can perform the shortest path exploration from each source node in parallel. Additionally, each of the shortest path computations can be done in parallel. Our implementation tries to exploit parallelism using the former approach, that is, by having different threads execute single shortest-path computations independently, and by using that information to compute the contribution from each individual source to the betweenness of each node in the graph. The process is described in Figure 1.

1 2 3 4 5 6 7 8 9 10 Graph g = /* read input graph */; Workset ws = new Workset(g.getNodes()) foreach (Node s : ws) { Perform forward BFS: compute BFS DAG for all nodes compute \(\sigma_{sv}\) For all nodes \(v\) in the BFS DAG: compute \(\delta_{s}(v)\) \(BC(v) += \delta_{s}(v)\) }

Figure 1: Pseudocode for Betweenness Centrality.

One thing to note is that, with the exception of line 9, the computations performed by different iterations are independent. The updates to the betweenness values in line 8, are simple reductions and do not generate conflicts. Additionally, since the this algorithm is compute-intensive, even for relatively small graphs, we can compute an approximation of the betweenness value by populating the worklist (line 2) with only a subset of the graph nodes as shortest-path sources.

Data Structures

There are two key data structures used in betweenness centrality:

Unordered Set
The subset of the graph nodes that serve as sources of shortest path explorations is represented as an unordered set. The nodes can be processed in any order.
Graph
The input graph.

Performance

Figure 2: Performance results on a scale-free graph with 2^14 nodes and 8*2^24 edges edges, generated by the the tools provided with SSCA v2.2 [2]. The generator is based on the Recursive MATrix (R-MAT) scale-free graph generation algorithm [3]. On the same input, the version of betweenness centrality provided in [2] takes 39.6 seconds (shown as Serial in the figure).

[1] Ulrik Brandes: A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology 2001.

[2] http://www.graphanalysis.org/benchmark/

[3] D. Chakrabarti, Y. Zhan, and C. Faloutsos, R-MAT: A recursive model for graph mining, SIAM Data Mining 2004.

Machine Description

Performance numbers are collected on a 4 package, 10 cores per package, Intel Xeon E7-4860 machine at 2.27GHz. Thread numbers above 40 use SMT. The machine has 128GB of ram with 20GB dedicated to 2M hugepages used by the Galois allocator. The operating system is Ubuntu Linux 10.04 LTS (Linux 2.6.32). All runs of the Galois benchmarks used gcc/g++ 4.7 to compile with a patch to the C++ runtime to improve the scalability of exception handling. All other implementations were compiled with Intel ICC 12.1 with thread parallelization provided by Intel Cilk.