Centrality#
This module is meant for all functions related to centrality in networks.
Return the centrality betweenness of \(G\) 

Return the k most closeness central vertices of \(G\) 

Return an estimation of the closeness centrality of \(G\). 
Functions#
 sage.graphs.centrality.centrality_betweenness(G, exact=False, normalize=True)[source]#
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 {n1} 2\) (for graphs) or \(2\binom {n1} 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,\ldots,v_k\) be the outneighbors 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,\ldots,v_k\) associated with each \(v\).
EXAMPLES:
sage: from sage.graphs.centrality import centrality_betweenness sage: centrality_betweenness(digraphs.Circuit(6)) # abs tol 1e10 {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 1e10 {0: 0.2, 1: 0.2, 2: 0.2, 3: 0.2, 4: 0.2, 5: 0.2}
>>> from sage.all import * >>> from sage.graphs.centrality import centrality_betweenness >>> centrality_betweenness(digraphs.Circuit(Integer(6))) # abs tol 1e10 {0: 0.5, 1: 0.5, 2: 0.5, 3: 0.5, 4: 0.5, 5: 0.5} >>> centrality_betweenness(graphs.CycleGraph(Integer(6))) # abs tol 1e10 {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}
>>> from sage.all import * >>> 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}
 sage.graphs.centrality.centrality_closeness_random_k(G, k=1)[source]#
Return an estimation of the closeness centrality of \(G\).
The algorithm first randomly selects a set \(S\) of \(k\) vertices. Then it computes shortest path distances from each vertex in \(S\) (using Dijkstra for weighted graph and breadthfirstsearch (BFS) for unweighted graph) and uses this knowledge to estimate the closeness centrality of all vertices.
For more information, see [EDI2014].
INPUT:
G
– an undirected connected Graphk
– integer (default: 1); number of random nodes to choose
OUTPUT:
A dictionary associating to each vertex its estimated closeness centrality.
EXAMPLES:
Estimation of the closeness centrality of the Petersen Graph when \(k == n\):
sage: from sage.graphs.centrality import centrality_closeness_random_k sage: G = graphs.PetersenGraph() sage: centrality_closeness_random_k(G, 10) {0: 0.6, 1: 0.6, 2: 0.6, 3: 0.6, 4: 0.6, 5: 0.6, 6: 0.6, 7: 0.6, 8: 0.6, 9: 0.6}
>>> from sage.all import * >>> from sage.graphs.centrality import centrality_closeness_random_k >>> G = graphs.PetersenGraph() >>> centrality_closeness_random_k(G, Integer(10)) {0: 0.6, 1: 0.6, 2: 0.6, 3: 0.6, 4: 0.6, 5: 0.6, 6: 0.6, 7: 0.6, 8: 0.6, 9: 0.6}
 sage.graphs.centrality.centrality_closeness_top_k(G, k=1, verbose=0)[source]#
Compute the
k
vertices with largest closeness centrality.The algorithm is based on performing a breadthfirstsearch (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 withcentrality_closeness()
. Conversely, ifk
is close to the number of nodes, the runningtime 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); define 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)\), where \(v\) is one of thek
most central vertices, and \(closv\) is its closeness centrality. If \(k\) is bigger than the number of vertices with positive (out)degree, the list might be smaller.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)]
>>> from sage.all import * >>> from sage.graphs.centrality import centrality_closeness_top_k >>> g = graphs.PathGraph(Integer(10)) >>> centrality_closeness_top_k(g, Integer(4), Integer(1)) Final performance ratio: 0.711111111111... [(0.36, 5), (0.36, 4), (0.3333333333333333, 6), (0.3333333333333333, 3)] >>> g = digraphs.Path(Integer(10)) >>> centrality_closeness_top_k(g, Integer(5), Integer(1)) Final performance ratio: 0.422222222222... [(0.2, 0), (0.19753086419753085, 1), (0.19444444444444442, 2), (0.19047619047619047, 3), (0.18518518518518517, 4)]