### Documentation / Algorithms

# Betweenness Centrality

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.

## Usage

This algorithm, by default, stores the centrality values for each edge inside
the `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 `setWeightAttributeName(String)`

method.
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 `Cb`

attribute. You can change the name of this attribute using the dedicated
constructor or the `setCentralityAttributeName(String)`

method.

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 `registerProgressIndicator(Progress)`

method.

## Complexity

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).

## Example

Here is an example of use:

## Reference

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,
- 2001,
- 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,
- 2008,
- issn 0378-8733,
- DOI: 10.1016/j.socnet.2007.11.001