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\)
centrality_closeness_random_k() Return an estimation of the closeness centrality 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,\ldots,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,\ldots,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}
sage.graphs.centrality.centrality_closeness_random_k(G, k=1)

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 breadth-first-search (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 Graph
  • k – 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}
sage.graphs.centrality.centrality_closeness_top_k(G, k=1, verbose=0)

Compute 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 the k 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. If k 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 the k 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)]