Centrality¶
This module is meant for all functions related to centrality in networks.
centrality_betweenness() |
Return the centrality betweenness of \(G\) |
centrality_closeness_top_k() |
Return the k most closeness central vertices 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)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 \(\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
-
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)]
TESTS:
If
k
orverbose
is not an integer:sage: from sage.graphs.centrality import centrality_closeness_top_k sage: g = digraphs.Path(10) sage: centrality_closeness_top_k(g, 'abc', 1) Traceback (most recent call last): ... TypeError: an integer is required sage: centrality_closeness_top_k(g, 1, 'abc') Traceback (most recent call last): ... TypeError: an integer is required
If
k
is bigger than the number of nodes:sage: from sage.graphs.centrality import centrality_closeness_top_k sage: g = graphs.PathGraph(5) sage: centrality_closeness_top_k(g, 10, 0) [(0.6666666666666666, 2), (0.5714285714285714, 3), (0.5714285714285714, 1), (0.4, 4), (0.4, 0)]
Empty graph:
sage: from sage.graphs.centrality import centrality_closeness_top_k sage: g = Graph() sage: centrality_closeness_top_k(g, 10, 0) [] sage: g = Graph(10) sage: centrality_closeness_top_k(g, 10, 0) []
The result is correct:
sage: from sage.graphs.centrality import centrality_closeness_top_k sage: import random sage: n = 20 sage: m = random.randint(1, n*(n-1) / 2) sage: k = random.randint(1, n) sage: g = graphs.RandomGNM(n,m) sage: topk = centrality_closeness_top_k(g, k) sage: centr = g.centrality_closeness(algorithm='BFS') sage: sorted_centr = sorted(centr.values(), reverse=True) sage: assert(len(topk)==min(k, len(sorted_centr))) sage: for i in range(len(topk)): ....: assert(abs(topk[i][0] - sorted_centr[i]) < 1e-12)
Directed case:
sage: from sage.graphs.centrality import centrality_closeness_top_k sage: import random sage: n = 20 sage: m = random.randint(1, n*(n-1)) sage: k = random.randint(1, n) sage: g = digraphs.RandomDirectedGNM(n,m) sage: topk = centrality_closeness_top_k(g, k) sage: centr = g.centrality_closeness(algorithm='BFS') sage: sorted_centr = sorted(centr.values(), reverse=True) sage: assert(len(topk)==min(k, len(sorted_centr))) sage: for i in range(len(topk)): ....: assert(abs(topk[i][0] - sorted_centr[i]) < 1e-12)