blob: 19fd7efb222839c885717afde107841db430bc2d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
# Brandes' Algorithm
A parallel implementation of Brandes' algorithm for calculating [betweenness
centrality](https://en.wikipedia.org/wiki/Betweenness_centrality) in unweighted
graphs.
## Building
mkdir build
cd build
cmake ..
make
## Running
./brandes <number threads> <input file> <output file>
### Graph representation
This implementation expects a simple, directed, unweighted graph with vertices
labeled with integers.
Sample input file:
0 2
2 0
2 3
2 4
3 2
3 5
3 6
Here each line represents a directed edge from the first node to the second.
The output will contain a line for each node with at least one out edge, of the
form `<node> <BC[node]>`. Thus for the above sample input, the output file
should contain:
0 0
2 6
3 4
## Links
* [*A Faster Algorithm for Betweenness Centrality*
](https://kops.uni-konstanz.de/bitstream/handle/123456789/5739/algorithm.pdf?sequence=1)
(U. Brandes)
* [*Parallel Algorithms for Evaluating Centrality Indices in Real-World Networks*
](https://smartech.gatech.edu/bitstream/handle/1853/14428/GT-CSE-06-13.pdf)
(D. A. Bader, K. Madduri)
|