Centrality¶
This module is meant for all functions related to centrality in networks.
centrality_betweenness() |
Return the centrality betweenness of ![]() |
Functions¶
-
sage.graphs.centrality.
centrality_betweenness
(G, exact=False, normalize=True)¶ Return the centrality betweenness of
The centrality betweenness of a vertex
is defined by:
For more information, see the Wikipedia article Betweenness_centrality.
INPUT:
G
– a (di)graphexact
(boolean, default:False
) – whether to compute over rationals or ondouble
C variables.normalize
(boolean; default:True
) – whether to renormalize the values by dividing them by(for graphs) or
(for digraphs).
ALGORITHM:
To compute
, we fix
and define
as the centrality of
due to
, obtained from the formula above by running the sum over
only. We obtain
.
For every vertex
, we compute the value of
for all
, using the following remark (see [Brandes01]):
Let
be the out-neighbors of
such that
. Then
The number of shortest paths between
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
associated with each
.
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