Document

prominent_group(G, k, weight=None, C=None, endpoints=False, normalized=True, greedy=False)

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(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\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$).

Notes

Group betweenness centrality is described in and its importance discussed in . The algorithm is described in and is based on techniques mentioned in .

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.

The total number of paths between source and target is counted differently for directed and undirected graphs. Directed paths between "u" and "v" are counted as two possible paths (one each direction) while undirected paths between "u" and "v" are counted as one path. Said another way, the sum in the expression above is over all s != t for directed graphs and for s < t for undirected graphs.

Parameters

G : graph: A NetworkX graph.
k : int: The number of nodes in the group.
normalized : bool, optional (default=True): If True, group betweenness is normalized by 1/((|V|-|C|)(|V|-|C|-1)) 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. The weight of an edge is treated as the length or distance between the two sides.
endpoints : bool, optional (default=False): If True include the endpoints in the shortest path counts.
C : list or set, optional (default=None): list of nodes which won't be candidates of the prominent group.
greedy : bool, optional (default=False): Using a naive greedy algorithm in order to find non-optimal prominent group. For scale free networks the results are negligibly below the optimal results.

Raises

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

Returns

max_GBC : float: The group betweenness centrality of the prominent group.
max_group : list: The list of nodes in the prominent group.

Find the prominent group of size $k$ in graph $G$. The prominence of the group is evaluated by the group betweenness centrality.

Examples

See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them