BetweennessCentrality

Betweenness centrality.

Computes the betweenness centrality of each vertex of a graph. The betweenness centrality of a node $v$ is given by the expression: $g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}$ where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma_{st}(v)$ is the number of those paths that pass through $v$. For more details see wikipedia.

The algorithm is based on

• Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality". Journal of Mathematical Sociology. 25 (2): 163–177.

The running time is $O(nm)$ for unweighted graphs, where $n$ is the number of vertices and $m$ the number of edges of the graph. The space complexity is $O(n + m)$.

Note that this running time assumes that arithmetic is performed between numbers whose representation needs a number of bits which is logarithmic in the instance size. There are instances where this is not true and path counters might grow super exponential. This class allows the user to adjust whether an exception is thrown in case overflow occurs. Default behavior is to ignore overflow issues.

Author

Assaf Mizrachi

Parameters