Centrality

This module is meant for all functions related to centrality in networks.

centrality_betweenness() Return the centrality betweenness of G

Functions

sage.graphs.centrality.centrality_betweenness(G, exact=False, normalize=True)

Return the centrality betweenness of G

The centrality betweenness of a vertex v\in G is defined by:

c(v) = \sum_{s\neq v \neq t} \frac{\#\{\text{shortest } st-\text{paths containing v}\}}
                                  {\#\{\text{shortest } st-\text{paths}\}}

For more information, see the Wikipedia article Betweenness_centrality.

INPUT:

  • G – a (di)graph
  • exact (boolean, default: False) – whether to compute over rationals or on double C variables.
  • normalize (boolean; default: True) – whether to renormalize the values by dividing them by \binom {n-1} 2 (for graphs) or 2\binom {n-1}
2 (for digraphs).

ALGORITHM:

To compute c(v), we fix s and define c_s(v) as the centrality of v due to s, obtained from the formula above by running the sum over t only. We obtain c(v)=\sum_{s\neq v} c_s(v).

For every vertex s, we compute the value of c_s(v) for all v, using the following remark (see [Brandes01]):

Let v_1,...,v_k be the out-neighbors of v such that dist(s,v_i)=dist(s,v)+1. Then

c_s(v) = \sum_{1\leq i \leq k} c_s(v_i)
             \frac{\#\{\text{shortest } sv_i-\text{paths}\}}
                  {\#\{\text{shortest } sv  -\text{paths}\}}

The number of shortest paths between s and every other vertex can be computed with a slightly modified BFS. While running this BFS we can also store the list of the vertices v_1,...,v_k associated with each v.

EXAMPLES:

sage: from sage.graphs.centrality import centrality_betweenness
sage: centrality_betweenness(digraphs.Circuit(6)) # abs tol 1e-10
{0: 0.5, 1: 0.5, 2: 0.5, 3: 0.5, 4: 0.5, 5: 0.5}
sage: centrality_betweenness(graphs.CycleGraph(6)) # abs tol 1e-10
{0: 0.2, 1: 0.2, 2: 0.2, 3: 0.2, 4: 0.2, 5: 0.2}

Exact computations:

sage: graphs.PetersenGraph().centrality_betweenness(exact=True)
{0: 1/12, 1: 1/12, 2: 1/12, 3: 1/12, 4: 1/12, 5: 1/12, 6: 1/12, 7: 1/12, 8: 1/12, 9: 1/12}

TESTS:

Compare with NetworkX:

sage: import networkx
sage: g = graphs.RandomGNP(100,.2)
sage: nw = networkx.betweenness_centrality(g.networkx_graph(copy=False))
sage: sg = centrality_betweenness(g)
sage: max(abs(nw[x]-sg[x]) for x in g) # abs tol 1e-10
0

Stupid cases:

sage: centrality_betweenness(Graph())
{}
sage: centrality_betweenness(Graph(2))
{0: 0.0, 1: 0.0}
sage: centrality_betweenness(Graph(2),exact=1)
{0: 0, 1: 0}

REFERENCES:

[Brandes01]Ulrik Brandes, A faster algorithm for betweenness centrality, Journal of Mathematical Sociology 25.2 (2001): 163-177, http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf