aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py787
1 files changed, 787 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py
new file mode 100644
index 00000000..7c48742a
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/centrality/group.py
@@ -0,0 +1,787 @@
+"""Group centrality measures."""
+
+from copy import deepcopy
+
+import networkx as nx
+from networkx.algorithms.centrality.betweenness import (
+ _accumulate_endpoints,
+ _single_source_dijkstra_path_basic,
+ _single_source_shortest_path_basic,
+)
+from networkx.utils.decorators import not_implemented_for
+
+__all__ = [
+ "group_betweenness_centrality",
+ "group_closeness_centrality",
+ "group_degree_centrality",
+ "group_in_degree_centrality",
+ "group_out_degree_centrality",
+ "prominent_group",
+]
+
+
+@nx._dispatchable(edge_attrs="weight")
+def group_betweenness_centrality(G, C, normalized=True, weight=None, endpoints=False):
+ r"""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$
+
+ .. math::
+
+ 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$).
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+
+ C : list or set or list of lists or list of sets
+ A group or a list of groups containing nodes which belong to G, for which group betweenness
+ centrality is to be calculated.
+
+ 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.
+
+ Raises
+ ------
+ NodeNotFound
+ If node(s) in C are not present in G.
+
+ Returns
+ -------
+ betweenness : list of floats or float
+ If C is a single group then return a float. If C is a list with
+ several groups then return a list of group betweenness centralities.
+
+ See Also
+ --------
+ betweenness_centrality
+
+ Notes
+ -----
+ Group betweenness centrality is described in [1]_ and its importance discussed in [3]_.
+ The initial implementation of the algorithm is mentioned in [2]_. This function uses
+ an improved algorithm presented in [4]_.
+
+ 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.
+
+
+ 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
+ .. [4] Rami Puzis, Yuval Elovici, and Shlomi Dolev.
+ "Fast algorithm for successive computation of group betweenness centrality."
+ https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709
+
+ """
+ GBC = [] # initialize betweenness
+ list_of_groups = True
+ # check weather C contains one or many groups
+ if any(el in G for el in C):
+ C = [C]
+ list_of_groups = False
+ set_v = {node for group in C for node in group}
+ if set_v - G.nodes: # element(s) of C not in G
+ raise nx.NodeNotFound(f"The node(s) {set_v - G.nodes} are in C but not in G.")
+
+ # pre-processing
+ PB, sigma, D = _group_preprocessing(G, set_v, weight)
+
+ # the algorithm for each group
+ for group in C:
+ group = set(group) # set of nodes in group
+ # initialize the matrices of the sigma and the PB
+ GBC_group = 0
+ sigma_m = deepcopy(sigma)
+ PB_m = deepcopy(PB)
+ sigma_m_v = deepcopy(sigma_m)
+ PB_m_v = deepcopy(PB_m)
+ for v in group:
+ GBC_group += PB_m[v][v]
+ for x in group:
+ for y in group:
+ dxvy = 0
+ dxyv = 0
+ dvxy = 0
+ if not (
+ sigma_m[x][y] == 0 or sigma_m[x][v] == 0 or sigma_m[v][y] == 0
+ ):
+ if D[x][v] == D[x][y] + D[y][v]:
+ dxyv = sigma_m[x][y] * sigma_m[y][v] / sigma_m[x][v]
+ if D[x][y] == D[x][v] + D[v][y]:
+ dxvy = sigma_m[x][v] * sigma_m[v][y] / sigma_m[x][y]
+ if D[v][y] == D[v][x] + D[x][y]:
+ dvxy = sigma_m[v][x] * sigma[x][y] / sigma[v][y]
+ sigma_m_v[x][y] = sigma_m[x][y] * (1 - dxvy)
+ PB_m_v[x][y] = PB_m[x][y] - PB_m[x][y] * dxvy
+ if y != v:
+ PB_m_v[x][y] -= PB_m[x][v] * dxyv
+ if x != v:
+ PB_m_v[x][y] -= PB_m[v][y] * dvxy
+ sigma_m, sigma_m_v = sigma_m_v, sigma_m
+ PB_m, PB_m_v = PB_m_v, PB_m
+
+ # endpoints
+ v, c = len(G), len(group)
+ if not endpoints:
+ scale = 0
+ # if the graph is connected then subtract the endpoints from
+ # the count for all the nodes in the graph. else count how many
+ # nodes are connected to the group's nodes and subtract that.
+ if nx.is_directed(G):
+ if nx.is_strongly_connected(G):
+ scale = c * (2 * v - c - 1)
+ elif nx.is_connected(G):
+ scale = c * (2 * v - c - 1)
+ if scale == 0:
+ for group_node1 in group:
+ for node in D[group_node1]:
+ if node != group_node1:
+ if node in group:
+ scale += 1
+ else:
+ scale += 2
+ GBC_group -= scale
+
+ # normalized
+ if normalized:
+ scale = 1 / ((v - c) * (v - c - 1))
+ GBC_group *= scale
+
+ # If undirected than count only the undirected edges
+ elif not G.is_directed():
+ GBC_group /= 2
+
+ GBC.append(GBC_group)
+ if list_of_groups:
+ return GBC
+ return GBC[0]
+
+
+def _group_preprocessing(G, set_v, weight):
+ sigma = {}
+ delta = {}
+ D = {}
+ betweenness = dict.fromkeys(G, 0)
+ for s in G:
+ if weight is None: # use BFS
+ S, P, sigma[s], D[s] = _single_source_shortest_path_basic(G, s)
+ else: # use Dijkstra's algorithm
+ S, P, sigma[s], D[s] = _single_source_dijkstra_path_basic(G, s, weight)
+ betweenness, delta[s] = _accumulate_endpoints(betweenness, S, P, sigma[s], s)
+ for i in delta[s]: # add the paths from s to i and rescale sigma
+ if s != i:
+ delta[s][i] += 1
+ if weight is not None:
+ sigma[s][i] = sigma[s][i] / 2
+ # building the path betweenness matrix only for nodes that appear in the group
+ PB = dict.fromkeys(G)
+ for group_node1 in set_v:
+ PB[group_node1] = dict.fromkeys(G, 0.0)
+ for group_node2 in set_v:
+ if group_node2 not in D[group_node1]:
+ continue
+ for node in G:
+ # if node is connected to the two group nodes than continue
+ if group_node2 in D[node] and group_node1 in D[node]:
+ if (
+ D[node][group_node2]
+ == D[node][group_node1] + D[group_node1][group_node2]
+ ):
+ PB[group_node1][group_node2] += (
+ delta[node][group_node2]
+ * sigma[node][group_node1]
+ * sigma[group_node1][group_node2]
+ / sigma[node][group_node2]
+ )
+ return PB, sigma, D
+
+
+@nx._dispatchable(edge_attrs="weight")
+def prominent_group(
+ G, k, weight=None, C=None, endpoints=False, normalized=True, greedy=False
+):
+ r"""Find the prominent group of size $k$ in graph $G$. The prominence of the
+ group is evaluated by the 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 vertex in $C$
+
+ .. math::
+
+ 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$).
+
+ 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.
+
+ See Also
+ --------
+ betweenness_centrality, group_betweenness_centrality
+
+ Notes
+ -----
+ Group betweenness centrality is described in [1]_ and its importance discussed in [3]_.
+ The algorithm is described in [2]_ and is based on techniques mentioned in [4]_.
+
+ 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.
+
+ 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] Rami Puzis, Yuval Elovici, and Shlomi Dolev:
+ "Finding the Most Prominent Group in Complex Networks"
+ AI communications 20(4): 287-296, 2007.
+ https://www.researchgate.net/profile/Rami_Puzis2/publication/220308855
+ .. [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
+ .. [4] Rami Puzis, Yuval Elovici, and Shlomi Dolev.
+ "Fast algorithm for successive computation of group betweenness centrality."
+ https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709
+ """
+ import numpy as np
+ import pandas as pd
+
+ if C is not None:
+ C = set(C)
+ if C - G.nodes: # element(s) of C not in G
+ raise nx.NodeNotFound(f"The node(s) {C - G.nodes} are in C but not in G.")
+ nodes = list(G.nodes - C)
+ else:
+ nodes = list(G.nodes)
+ DF_tree = nx.Graph()
+ DF_tree.__networkx_cache__ = None # Disable caching
+ PB, sigma, D = _group_preprocessing(G, nodes, weight)
+ betweenness = pd.DataFrame.from_dict(PB)
+ if C is not None:
+ for node in C:
+ # remove from the betweenness all the nodes not part of the group
+ betweenness.drop(index=node, inplace=True)
+ betweenness.drop(columns=node, inplace=True)
+ CL = [node for _, node in sorted(zip(np.diag(betweenness), nodes), reverse=True)]
+ max_GBC = 0
+ max_group = []
+ DF_tree.add_node(
+ 1,
+ CL=CL,
+ betweenness=betweenness,
+ GBC=0,
+ GM=[],
+ sigma=sigma,
+ cont=dict(zip(nodes, np.diag(betweenness))),
+ )
+
+ # the algorithm
+ DF_tree.nodes[1]["heu"] = 0
+ for i in range(k):
+ DF_tree.nodes[1]["heu"] += DF_tree.nodes[1]["cont"][DF_tree.nodes[1]["CL"][i]]
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, 1, D, max_group, nodes, greedy
+ )
+
+ v = len(G)
+ if not endpoints:
+ scale = 0
+ # if the graph is connected then subtract the endpoints from
+ # the count for all the nodes in the graph. else count how many
+ # nodes are connected to the group's nodes and subtract that.
+ if nx.is_directed(G):
+ if nx.is_strongly_connected(G):
+ scale = k * (2 * v - k - 1)
+ elif nx.is_connected(G):
+ scale = k * (2 * v - k - 1)
+ if scale == 0:
+ for group_node1 in max_group:
+ for node in D[group_node1]:
+ if node != group_node1:
+ if node in max_group:
+ scale += 1
+ else:
+ scale += 2
+ max_GBC -= scale
+
+ # normalized
+ if normalized:
+ scale = 1 / ((v - k) * (v - k - 1))
+ max_GBC *= scale
+
+ # If undirected then count only the undirected edges
+ elif not G.is_directed():
+ max_GBC /= 2
+ max_GBC = float(f"{max_GBC:.2f}")
+ return max_GBC, max_group
+
+
+def _dfbnb(G, k, DF_tree, max_GBC, root, D, max_group, nodes, greedy):
+ # stopping condition - if we found a group of size k and with higher GBC then prune
+ if len(DF_tree.nodes[root]["GM"]) == k and DF_tree.nodes[root]["GBC"] > max_GBC:
+ return DF_tree.nodes[root]["GBC"], DF_tree, DF_tree.nodes[root]["GM"]
+ # stopping condition - if the size of group members equal to k or there are less than
+ # k - |GM| in the candidate list or the heuristic function plus the GBC is below the
+ # maximal GBC found then prune
+ if (
+ len(DF_tree.nodes[root]["GM"]) == k
+ or len(DF_tree.nodes[root]["CL"]) <= k - len(DF_tree.nodes[root]["GM"])
+ or DF_tree.nodes[root]["GBC"] + DF_tree.nodes[root]["heu"] <= max_GBC
+ ):
+ return max_GBC, DF_tree, max_group
+
+ # finding the heuristic of both children
+ node_p, node_m, DF_tree = _heuristic(k, root, DF_tree, D, nodes, greedy)
+
+ # finding the child with the bigger heuristic + GBC and expand
+ # that node first if greedy then only expand the plus node
+ if greedy:
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy
+ )
+
+ elif (
+ DF_tree.nodes[node_p]["GBC"] + DF_tree.nodes[node_p]["heu"]
+ > DF_tree.nodes[node_m]["GBC"] + DF_tree.nodes[node_m]["heu"]
+ ):
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy
+ )
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, node_m, D, max_group, nodes, greedy
+ )
+ else:
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, node_m, D, max_group, nodes, greedy
+ )
+ max_GBC, DF_tree, max_group = _dfbnb(
+ G, k, DF_tree, max_GBC, node_p, D, max_group, nodes, greedy
+ )
+ return max_GBC, DF_tree, max_group
+
+
+def _heuristic(k, root, DF_tree, D, nodes, greedy):
+ import numpy as np
+
+ # This helper function add two nodes to DF_tree - one left son and the
+ # other right son, finds their heuristic, CL, GBC, and GM
+ node_p = DF_tree.number_of_nodes() + 1
+ node_m = DF_tree.number_of_nodes() + 2
+ added_node = DF_tree.nodes[root]["CL"][0]
+
+ # adding the plus node
+ DF_tree.add_nodes_from([(node_p, deepcopy(DF_tree.nodes[root]))])
+ DF_tree.nodes[node_p]["GM"].append(added_node)
+ DF_tree.nodes[node_p]["GBC"] += DF_tree.nodes[node_p]["cont"][added_node]
+ root_node = DF_tree.nodes[root]
+ for x in nodes:
+ for y in nodes:
+ dxvy = 0
+ dxyv = 0
+ dvxy = 0
+ if not (
+ root_node["sigma"][x][y] == 0
+ or root_node["sigma"][x][added_node] == 0
+ or root_node["sigma"][added_node][y] == 0
+ ):
+ if D[x][added_node] == D[x][y] + D[y][added_node]:
+ dxyv = (
+ root_node["sigma"][x][y]
+ * root_node["sigma"][y][added_node]
+ / root_node["sigma"][x][added_node]
+ )
+ if D[x][y] == D[x][added_node] + D[added_node][y]:
+ dxvy = (
+ root_node["sigma"][x][added_node]
+ * root_node["sigma"][added_node][y]
+ / root_node["sigma"][x][y]
+ )
+ if D[added_node][y] == D[added_node][x] + D[x][y]:
+ dvxy = (
+ root_node["sigma"][added_node][x]
+ * root_node["sigma"][x][y]
+ / root_node["sigma"][added_node][y]
+ )
+ DF_tree.nodes[node_p]["sigma"][x][y] = root_node["sigma"][x][y] * (1 - dxvy)
+ DF_tree.nodes[node_p]["betweenness"].loc[y, x] = (
+ root_node["betweenness"][x][y] - root_node["betweenness"][x][y] * dxvy
+ )
+ if y != added_node:
+ DF_tree.nodes[node_p]["betweenness"].loc[y, x] -= (
+ root_node["betweenness"][x][added_node] * dxyv
+ )
+ if x != added_node:
+ DF_tree.nodes[node_p]["betweenness"].loc[y, x] -= (
+ root_node["betweenness"][added_node][y] * dvxy
+ )
+
+ DF_tree.nodes[node_p]["CL"] = [
+ node
+ for _, node in sorted(
+ zip(np.diag(DF_tree.nodes[node_p]["betweenness"]), nodes), reverse=True
+ )
+ if node not in DF_tree.nodes[node_p]["GM"]
+ ]
+ DF_tree.nodes[node_p]["cont"] = dict(
+ zip(nodes, np.diag(DF_tree.nodes[node_p]["betweenness"]))
+ )
+ DF_tree.nodes[node_p]["heu"] = 0
+ for i in range(k - len(DF_tree.nodes[node_p]["GM"])):
+ DF_tree.nodes[node_p]["heu"] += DF_tree.nodes[node_p]["cont"][
+ DF_tree.nodes[node_p]["CL"][i]
+ ]
+
+ # adding the minus node - don't insert the first node in the CL to GM
+ # Insert minus node only if isn't greedy type algorithm
+ if not greedy:
+ DF_tree.add_nodes_from([(node_m, deepcopy(DF_tree.nodes[root]))])
+ DF_tree.nodes[node_m]["CL"].pop(0)
+ DF_tree.nodes[node_m]["cont"].pop(added_node)
+ DF_tree.nodes[node_m]["heu"] = 0
+ for i in range(k - len(DF_tree.nodes[node_m]["GM"])):
+ DF_tree.nodes[node_m]["heu"] += DF_tree.nodes[node_m]["cont"][
+ DF_tree.nodes[node_m]["CL"][i]
+ ]
+ else:
+ node_m = None
+
+ return node_p, node_m, DF_tree
+
+
+@nx._dispatchable(edge_attrs="weight")
+def group_closeness_centrality(G, S, weight=None):
+ r"""Compute the group closeness centrality for a group of nodes.
+
+ Group closeness centrality of a group of nodes $S$ is a measure
+ of how close the group is to the other nodes in the graph.
+
+ .. math::
+
+ c_{close}(S) = \frac{|V-S|}{\sum_{v \in V-S} d_{S, v}}
+
+ d_{S, v} = min_{u \in S} (d_{u, v})
+
+ where $V$ is the set of nodes, $d_{S, v}$ is the distance of
+ the group $S$ from $v$ defined as above. ($V-S$ is the set of nodes
+ in $V$ that are not in $S$).
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+
+ S : list or set
+ S is a group of nodes which belong to G, for which group closeness
+ centrality is to be calculated.
+
+ 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.
+
+ Raises
+ ------
+ NodeNotFound
+ If node(s) in S are not present in G.
+
+ Returns
+ -------
+ closeness : float
+ Group closeness centrality of the group S.
+
+ See Also
+ --------
+ closeness_centrality
+
+ Notes
+ -----
+ The measure was introduced in [1]_.
+ The formula implemented here is described in [2]_.
+
+ Higher values of closeness indicate greater centrality.
+
+ It is assumed that 1 / 0 is 0 (required in the case of directed graphs,
+ or when a shortest path length is 0).
+
+ The number of nodes in the group must be a maximum of n - 1 where `n`
+ is the total number of nodes in the graph.
+
+ For directed graphs, the incoming distance is utilized here. To use the
+ outward distance, act on `G.reverse()`.
+
+ 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] J. Zhao et. al.:
+ Measuring and Maximizing Group Closeness Centrality over
+ Disk Resident Graphs.
+ WWWConference Proceedings, 2014. 689-694.
+ https://doi.org/10.1145/2567948.2579356
+ """
+ if G.is_directed():
+ G = G.reverse() # reverse view
+ closeness = 0 # initialize to 0
+ V = set(G) # set of nodes in G
+ S = set(S) # set of nodes in group S
+ V_S = V - S # set of nodes in V but not S
+ shortest_path_lengths = nx.multi_source_dijkstra_path_length(G, S, weight=weight)
+ # accumulation
+ for v in V_S:
+ try:
+ closeness += shortest_path_lengths[v]
+ except KeyError: # no path exists
+ closeness += 0
+ try:
+ closeness = len(V_S) / closeness
+ except ZeroDivisionError: # 1 / 0 assumed as 0
+ closeness = 0
+ return closeness
+
+
+@nx._dispatchable
+def group_degree_centrality(G, S):
+ """Compute the group degree centrality for a group of nodes.
+
+ Group degree centrality of a group of nodes $S$ is the fraction
+ of non-group members connected to group members.
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+
+ S : list or set
+ S is a group of nodes which belong to G, for which group degree
+ centrality is to be calculated.
+
+ Raises
+ ------
+ NetworkXError
+ If node(s) in S are not in G.
+
+ Returns
+ -------
+ centrality : float
+ Group degree centrality of the group S.
+
+ See Also
+ --------
+ degree_centrality
+ group_in_degree_centrality
+ group_out_degree_centrality
+
+ Notes
+ -----
+ The measure was introduced in [1]_.
+
+ The number of nodes in the group must be a maximum of n - 1 where `n`
+ is the total number of nodes in the graph.
+
+ 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
+ """
+ centrality = len(set().union(*[set(G.neighbors(i)) for i in S]) - set(S))
+ centrality /= len(G.nodes()) - len(S)
+ return centrality
+
+
+@not_implemented_for("undirected")
+@nx._dispatchable
+def group_in_degree_centrality(G, S):
+ """Compute the group in-degree centrality for a group of nodes.
+
+ Group in-degree centrality of a group of nodes $S$ is the fraction
+ of non-group members connected to group members by incoming edges.
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+
+ S : list or set
+ S is a group of nodes which belong to G, for which group in-degree
+ centrality is to be calculated.
+
+ Returns
+ -------
+ centrality : float
+ Group in-degree centrality of the group S.
+
+ Raises
+ ------
+ NetworkXNotImplemented
+ If G is undirected.
+
+ NodeNotFound
+ If node(s) in S are not in G.
+
+ See Also
+ --------
+ degree_centrality
+ group_degree_centrality
+ group_out_degree_centrality
+
+ Notes
+ -----
+ The number of nodes in the group must be a maximum of n - 1 where `n`
+ is the total number of nodes in the graph.
+
+ `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph,
+ so for group in-degree centrality, the reverse graph is used.
+ """
+ return group_degree_centrality(G.reverse(), S)
+
+
+@not_implemented_for("undirected")
+@nx._dispatchable
+def group_out_degree_centrality(G, S):
+ """Compute the group out-degree centrality for a group of nodes.
+
+ Group out-degree centrality of a group of nodes $S$ is the fraction
+ of non-group members connected to group members by outgoing edges.
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+
+ S : list or set
+ S is a group of nodes which belong to G, for which group in-degree
+ centrality is to be calculated.
+
+ Returns
+ -------
+ centrality : float
+ Group out-degree centrality of the group S.
+
+ Raises
+ ------
+ NetworkXNotImplemented
+ If G is undirected.
+
+ NodeNotFound
+ If node(s) in S are not in G.
+
+ See Also
+ --------
+ degree_centrality
+ group_degree_centrality
+ group_in_degree_centrality
+
+ Notes
+ -----
+ The number of nodes in the group must be a maximum of n - 1 where `n`
+ is the total number of nodes in the graph.
+
+ `G.neighbors(i)` gives nodes with an outward edge from i, in a DiGraph,
+ so for group out-degree centrality, the graph itself is used.
+ """
+ return group_degree_centrality(G, S)