Compute the betweenness centrality of each vertex of a given graph.
The betweenness centrality counts how many shortest paths between each pair of nodes of the graph pass by a node. It does it for all nodes of the graph.
The above graph shows the betweenness centrality applied to a grid graph, where color indicates centrality, green is lower centrality and red is maximal centrality.
This algorithm, by default, stores the centrality values for each edge inside
Cb attribute. You can change this attribute name at construction time.
This algorithm does not accept multi-graphs (p-graphs with p>1) yet.
This algorithm does not take into account edge direction yet.
By default the
weight attribute name is
weight, you can activate the weights using
setWeighted(). You can change the weight attribute name using the
dedicated constructor or the
This method implicitly enable weights in the computation. Use
setUnweighted() to disable weights.
The result of the computation is stored on each node inside the
attribute. You can change the name of this attribute using the dedicated
constructor or the
As the computing of centrality can take a lot of time, you can provide a
progress callback to get notified each time the algorithm finished
processing a node (however the centrality values are usable only when the
algorithm finished). See the
By default the algorithm performs on a graph considered as not weighted with complexity O(nm). You can specify that the graph edges contain weights in which case the algorithm complexity is O(nm + n^2 log n).
Here is an example of use:
This is based on the algorithm described in “A Faster Algorithm for Betweenness Centrality”, Ulrik Brandes, Journal of Mathematical Sociology, 2001:
- A Faster Algorithm for Betweenness Centrality,
- Ulrik Brandes,
- Journal of Mathematical Sociology 25:2,
- pp. 163 - 177,
- DOI: 10.1080/0022250X.2001.9990249
And in “On variants of shortest-path betweenness centrality and their generic computation” , of the same author, 2008:
- On variants of shortest-path betweenness centrality and their generic computation,
- Ulrik Brandes,
- Social Networks 30:2,
- pp. 136 - 145,
- issn 0378-8733,
- DOI: 10.1016/j.socnet.2007.11.001