Centrality¶
This module is meant for all functions related to centrality in networks.
centrality_betweenness() |
Return the centrality betweenness of ![]() |
centrality_closeness_top_k() |
Return the k most closeness central vertices 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}
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
-
sage.graphs.centrality.
centrality_closeness_top_k
(G, k=1, verbose=0)¶ Computes the k vertices with largest closeness centrality.
The algorithm is based on performing a breadth-first-search (BFS) from each vertex, and to use bounds in order to cut these BFSes as soon as possible. If k is small, it is much more efficient than computing all centralities with
centrality_closeness()
. Conversely, if k is close to the number of nodes, the running-time is approximately the same (it might even be a bit longer, because more computations are needed). For more information, see [BCM15]. The algorithm does not work on weighted graphs.INPUT:
G
a Sage Graph or DiGraph;k
(integer, default: 1): the algorithm will return thek
vertices with largest closeness centrality. This value should be between 1 and the number of vertices with positive (out)degree, because the closeness centrality is not defined for vertices with (out)degree 0. Ifk
is bigger than this value, the output will contain all vertices of positive (out)degree.verbose
(integer, default: 0): an integer defining how “verbose” the algorithm should be. If 0, nothing is printed, if 1, we print only the performance ratio at the end of the algorithm, if 2, we print partial results every 1000 visits, if 3, we print partial results after every visit.
OUTPUT:
An ordered list of
k
pairs(closv, v)
, wherev
is one of thek
most central vertices, andclosv
is its closeness centrality. Ifk
is bigger than the number of vertices with positive (out)degree, the list might be smaller.REFERENCES:
[BCM15] Michele Borassi, Pierluigi Crescenzi, and Andrea Marino, Fast and Simple Computation of Top-k Closeness Centralities. Preprint on arXiv. http://arxiv.org/abs/1507.01490 EXAMPLES:
sage: from sage.graphs.centrality import centrality_closeness_top_k sage: g = graphs.PathGraph(10) sage: centrality_closeness_top_k(g, 4, 1) Final performance ratio: 0.711111111111 [(0.36, 5), (0.36, 4), (0.3333333333333333, 6), (0.3333333333333333, 3)] sage: g = digraphs.Path(10) sage: centrality_closeness_top_k(g, 5, 1) Final performance ratio: 0.422222222222 [(0.2, 0), (0.19753086419753085, 1), (0.19444444444444442, 2), (0.19047619047619047, 3), (0.18518518518518517, 4)]