Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Moody and White algorithm for k-components
3"""
5from collections import defaultdict
6from itertools import combinations
7from operator import itemgetter
9import networkx as nx
11# Define the default maximum flow function.
12from networkx.algorithms.flow import edmonds_karp
13from networkx.utils import not_implemented_for
15default_flow_func = edmonds_karp
17__all__ = ["k_components"]
20@not_implemented_for("directed")
21@nx._dispatchable
22def k_components(G, flow_func=None):
23 r"""Returns the k-component structure of a graph G.
25 A `k`-component is a maximal subgraph of a graph G that has, at least,
26 node connectivity `k`: we need to remove at least `k` nodes to break it
27 into more components. `k`-components have an inherent hierarchical
28 structure because they are nested in terms of connectivity: a connected
29 graph can contain several 2-components, each of which can contain
30 one or more 3-components, and so forth.
32 Parameters
33 ----------
34 G : NetworkX graph
36 flow_func : function
37 Function to perform the underlying flow computations. Default value
38 :meth:`edmonds_karp`. This function performs better in sparse graphs with
39 right tailed degree distributions. :meth:`shortest_augmenting_path` will
40 perform better in denser graphs.
42 Returns
43 -------
44 k_components : dict
45 Dictionary with all connectivity levels `k` in the input Graph as keys
46 and a list of sets of nodes that form a k-component of level `k` as
47 values.
49 Raises
50 ------
51 NetworkXNotImplemented
52 If the input graph is directed.
54 Examples
55 --------
56 >>> # Petersen graph has 10 nodes and it is triconnected, thus all
57 >>> # nodes are in a single component on all three connectivity levels
58 >>> G = nx.petersen_graph()
59 >>> k_components = nx.k_components(G)
61 Notes
62 -----
63 Moody and White [1]_ (appendix A) provide an algorithm for identifying
64 k-components in a graph, which is based on Kanevsky's algorithm [2]_
65 for finding all minimum-size node cut-sets of a graph (implemented in
66 :meth:`all_node_cuts` function):
68 1. Compute node connectivity, k, of the input graph G.
70 2. Identify all k-cutsets at the current level of connectivity using
71 Kanevsky's algorithm.
73 3. Generate new graph components based on the removal of
74 these cutsets. Nodes in a cutset belong to both sides
75 of the induced cut.
77 4. If the graph is neither complete nor trivial, return to 1;
78 else end.
80 This implementation also uses some heuristics (see [3]_ for details)
81 to speed up the computation.
83 See also
84 --------
85 node_connectivity
86 all_node_cuts
87 biconnected_components : special case of this function when k=2
88 k_edge_components : similar to this function, but uses edge-connectivity
89 instead of node-connectivity
91 References
92 ----------
93 .. [1] Moody, J. and D. White (2003). Social cohesion and embeddedness:
94 A hierarchical conception of social groups.
95 American Sociological Review 68(1), 103--28.
96 http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf
98 .. [2] Kanevsky, A. (1993). Finding all minimum-size separating vertex
99 sets in a graph. Networks 23(6), 533--541.
100 http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract
102 .. [3] Torrents, J. and F. Ferraro (2015). Structural Cohesion:
103 Visualization and Heuristics for Fast Computation.
104 https://arxiv.org/pdf/1503.04476v1
106 """
107 # Dictionary with connectivity level (k) as keys and a list of
108 # sets of nodes that form a k-component as values. Note that
109 # k-components can overlap (but only k - 1 nodes).
110 k_components = defaultdict(list)
111 # Define default flow function
112 if flow_func is None:
113 flow_func = default_flow_func
114 # Bicomponents as a base to check for higher order k-components
115 for component in nx.connected_components(G):
116 # isolated nodes have connectivity 0
117 comp = set(component)
118 if len(comp) > 1:
119 k_components[1].append(comp)
120 bicomponents = [G.subgraph(c) for c in nx.biconnected_components(G)]
121 for bicomponent in bicomponents:
122 bicomp = set(bicomponent)
123 # avoid considering dyads as bicomponents
124 if len(bicomp) > 2:
125 k_components[2].append(bicomp)
126 for B in bicomponents:
127 if len(B) <= 2:
128 continue
129 k = nx.node_connectivity(B, flow_func=flow_func)
130 if k > 2:
131 k_components[k].append(set(B))
132 # Perform cuts in a DFS like order.
133 cuts = list(nx.all_node_cuts(B, k=k, flow_func=flow_func))
134 stack = [(k, _generate_partition(B, cuts, k))]
135 while stack:
136 (parent_k, partition) = stack[-1]
137 try:
138 nodes = next(partition)
139 C = B.subgraph(nodes)
140 this_k = nx.node_connectivity(C, flow_func=flow_func)
141 if this_k > parent_k and this_k > 2:
142 k_components[this_k].append(set(C))
143 cuts = list(nx.all_node_cuts(C, k=this_k, flow_func=flow_func))
144 if cuts:
145 stack.append((this_k, _generate_partition(C, cuts, this_k)))
146 except StopIteration:
147 stack.pop()
149 # This is necessary because k-components may only be reported at their
150 # maximum k level. But we want to return a dictionary in which keys are
151 # connectivity levels and values list of sets of components, without
152 # skipping any connectivity level. Also, it's possible that subsets of
153 # an already detected k-component appear at a level k. Checking for this
154 # in the while loop above penalizes the common case. Thus we also have to
155 # _consolidate all connectivity levels in _reconstruct_k_components.
156 return _reconstruct_k_components(k_components)
159def _consolidate(sets, k):
160 """Merge sets that share k or more elements.
162 See: http://rosettacode.org/wiki/Set_consolidation
164 The iterative python implementation posted there is
165 faster than this because of the overhead of building a
166 Graph and calling nx.connected_components, but it's not
167 clear for us if we can use it in NetworkX because there
168 is no licence for the code.
170 """
171 G = nx.Graph()
172 nodes = dict(enumerate(sets))
173 G.add_nodes_from(nodes)
174 G.add_edges_from(
175 (u, v) for u, v in combinations(nodes, 2) if len(nodes[u] & nodes[v]) >= k
176 )
177 for component in nx.connected_components(G):
178 yield set.union(*[nodes[n] for n in component])
181def _generate_partition(G, cuts, k):
182 def has_nbrs_in_partition(G, node, partition):
183 return any(n in partition for n in G[node])
185 components = []
186 n_in_cuts = {n for cut in cuts for n in cut}
187 nodes = {n for n, d in G.degree() if d > k} - n_in_cuts
188 H = G.subgraph(nodes)
189 for cc in map(set, nx.connected_components(H)):
190 component = cc | {n for n in n_in_cuts if has_nbrs_in_partition(G, n, cc)}
191 if len(component) < G.order():
192 components.append(component)
193 yield from _consolidate(components, k + 1)
196def _reconstruct_k_components(k_comps):
197 result = {}
198 max_k = max(k_comps) if k_comps else 0
199 for k in range(max_k, 0, -1):
200 if k == max_k:
201 result[k] = list(_consolidate(k_comps[k], k))
202 elif k not in k_comps:
203 result[k] = list(_consolidate(result[k + 1], k))
204 else:
205 nodes_at_k = set.union(*k_comps[k])
206 to_add = [c for c in result[k + 1] if any(n not in nodes_at_k for n in c)]
207 if to_add:
208 result[k] = list(_consolidate(k_comps[k] + to_add, k))
209 else:
210 result[k] = list(_consolidate(k_comps[k], k))
211 return result
214def build_k_number_dict(kcomps):
215 return {
216 node: k
217 for k, comps in sorted(kcomps.items(), key=itemgetter(0))
218 for comp in comps
219 for node in comp
220 }