Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.centrality.group_betweenness_centrality

group_betweenness_centrality(G, C, normalized=True, weight=None)[source]

Compute the group betweenness centrality for a group of nodes.

Group betweenness centrality of a group of nodes \(C\) is the sum of the fraction of all-pairs shortest paths that pass through any vertex in \(C\)

\[c_B(C) =\sum_{s,t \in V-C; s<t} \frac{\sigma(s, t|C)}{\sigma(s, t)}\]

where \(V\) is the set of nodes, \(\sigma(s, t)\) is the number of shortest \((s, t)\)-paths, and \(\sigma(s, t|C)\) is the number of those paths passing through some node in group \(C\). Note that \((s, t)\) are not members of the group (\(V-C\) is the set of nodes in \(V\) that are not in \(C\)).

Parameters
  • G (graph) – A NetworkX graph.

  • C (list or set) – C is a group of nodes which belong to G, for which group betweenness centrality is to be calculated.

  • normalized (bool, optional) – If True, group betweenness is normalized by 2/((|V|-|C|)(|V|-|C|-1)) for graphs and 1/((|V|-|C|)(|V|-|C|-1)) for directed graphs where |V| is the number of nodes in G and |C| is the number of nodes in C.

  • weight (None or string, optional (default=None)) – If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight.

Raises

NodeNotFound – If node(s) in C are not present in G.

Returns

betweenness – Group betweenness centrality of the group C.

Return type

float

Notes

The measure is described in 1. The algorithm is an extension of the one proposed by Ulrik Brandes for betweenness centrality of nodes. Group betweenness is also mentioned in his paper 2 along with the algorithm. The importance of the measure is discussed in 3.

The number of nodes in the group must be a maximum of n - 2 where n is the total number of nodes in the graph.

For weighted graphs the edge weights must be greater than zero. Zero edge weights can produce an infinite number of equal length paths between pairs of nodes.

References

1

M G Everett and S P Borgatti: The Centrality of Groups and Classes. Journal of Mathematical Sociology. 23(3): 181-201. 1999. http://www.analytictech.com/borgatti/group_centrality.htm

2

Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.9610&rep=rep1&type=pdf

3

Sourav Medya et. al.: Group Centrality Maximization via Network Design. SIAM International Conference on Data Mining, SDM 2018, 126–134. https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf