prominent_group#

prominent_group(G, k, weight=None, C=None, endpoints=False, normalized=True, greedy=False)[source]#

Find the prominent group (and its centrality) of size \(k\) in graph \(G\).

The prominent group of nodes has the highest group betweenness centrality. Group betweenness centrality of a group of nodes \(C\) is the sum of the fraction of all-pairs shortest paths that pass through any node in \(C\)

\[c_B(v) =\sum_{s,t \in V-C} \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\) – see endpoints for other options).

Parameters:

Ggraph

A NetworkX graph.

kint

The number of nodes in the group.

normalizedbool, 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.

weightNone 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.

endpointsbool, optional (default=False)

By default, only node-pairs that are both not in the group are counted for group betweenness centrality. The count is how many non-C node-pairs have nodes from the group “between” them on a shortest path.

When endpoints=True, we also count node-pairs with one or both nodes in the group while considering endpoint nodes as being between the node-pairs. So we count paths that start in the group whether or not they pass through any other nodes in the group. This adds centrality to large groups without any reference to the connectivity of the group. The minimum normalized score is \(N_{in}(N_{in}-1)/(N(N-1))\) instead of 0. For that reason, this feature is rarely used.

We don’t currently support considering node-pairs with nodes in the group without also counting their endpoints. Nor do we support counting endpoints while only considering node-pairs that are both not in the group. This keyword indicates both counting endpoints of paths and allowing node-pairs in the group.

Clist or set, optional (default=None)

list of nodes which won’t be candidates of the prominent group.

greedybool, 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.

Returns:

max_GBC, max_group2-tuple of (float, list or nodes): A 2-tuple of the group betweenness centrality of the prominent group, and a list of nodes in the prominent group.

Raises:

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