Git repository for understanding Brandes' algorithm.
| Version | Date | Commit | Notes |
|---|---|---|---|
| 0.0 | April 23, 2021 | 79bd987 | first commit |
| 0.1 | April 23, 2021 | cb984f1 | Add graph class |
| 0.2 | April 24, 2021 | ba8818f | Added NetworkX betweenness centrality calculation program |
| 1.0 | April 24, 2021 | a1d86a4 | Completed betweenness centrality computation |
| 1.1 | April 24, 2021 | d5121e1 | time computation |
| 1.2 | April 24, 2021 | 4e8b78c | print normalized betweenness centrality |
The graph data files need to follow the rule below. <endpoint n> needs to be an int (node id)
<endpoint 1> <endpoint 2>
<endpoint 3> <endpoint 4>
.
.
.
Let's say there is a graph like this.
The following data (graph/simple_graph.gr) represents this simple graph with 9 nodes and 12 edges, which are <0, 1>, ..., <7, 8>.
0 1
0 2
1 2
1 3
2 3
2 7
3 4
3 5
4 6
5 6
5 8
7 8
Try the following command to get an instant result.
sh run.sh all graph/simple_graph.gr
- Brandes, Ulrik (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 25 (2): 163–177. CiteSeerX 10.1.1.11.2024. doi:10.1080/0022250x.2001.9990249. hdl:10983/23603. S2CID 13971996.