### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/kcomponents.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """ Fast approximation for k-component structure
2 """
3 import itertools
4 from collections import defaultdict
5 from collections.abc import Mapping
6
7 import networkx as nx
8 from networkx.exception import NetworkXError
9 from networkx.utils import not_implemented_for
10
11 from networkx.algorithms.approximation import local_node_connectivity
12
13
14 __all__ = ["k_components"]
15
16
17 not_implemented_for("directed")
18
19
20 def k_components(G, min_density=0.95):
21 r"""Returns the approximate k-component structure of a graph G.
22
23 A k-component is a maximal subgraph of a graph G that has, at least,
24 node connectivity k: we need to remove at least k nodes to break it
25 into more components. k-components have an inherent hierarchical
26 structure because they are nested in terms of connectivity: a connected
27 graph can contain several 2-components, each of which can contain
28 one or more 3-components, and so forth.
29
30 This implementation is based on the fast heuristics to approximate
31 the k-component structure of a graph _. Which, in turn, it is based on
32 a fast approximation algorithm for finding good lower bounds of the number
33 of node independent paths between two nodes _.
34
35 Parameters
36 ----------
37 G : NetworkX graph
38 Undirected graph
39
40 min_density : Float
41 Density relaxation threshold. Default value 0.95
42
43 Returns
44 -------
45 k_components : dict
46 Dictionary with connectivity level k as key and a list of
47 sets of nodes that form a k-component of level k as values.
48
49
50 Examples
51 --------
52 >>> # Petersen graph has 10 nodes and it is triconnected, thus all
53 >>> # nodes are in a single component on all three connectivity levels
54 >>> from networkx.algorithms import approximation as apxa
55 >>> G = nx.petersen_graph()
56 >>> k_components = apxa.k_components(G)
57
58 Notes
59 -----
60 The logic of the approximation algorithm for computing the k-component
61 structure _ is based on repeatedly applying simple and fast algorithms
62 for k-cores and biconnected components in order to narrow down the
63 number of pairs of nodes over which we have to compute White and Newman's
64 approximation algorithm for finding node independent paths _. More
65 formally, this algorithm is based on Whitney's theorem, which states
66 an inclusion relation among node connectivity, edge connectivity, and
67 minimum degree for any graph G. This theorem implies that every
68 k-component is nested inside a k-edge-component, which in turn,
69 is contained in a k-core. Thus, this algorithm computes node independent
70 paths among pairs of nodes in each biconnected part of each k-core,
71 and repeats this procedure for each k from 3 to the maximal core number
72 of a node in the input graph.
73
74 Because, in practice, many nodes of the core of level k inside a
75 bicomponent actually are part of a component of level k, the auxiliary
76 graph needed for the algorithm is likely to be very dense. Thus, we use
77 a complement graph data structure (see AntiGraph) to save memory.
78 AntiGraph only stores information of the edges that are *not* present
79 in the actual auxiliary graph. When applying algorithms to this
80 complement graph data structure, it behaves as if it were the dense
81 version.
82
84 --------
85 k_components
86
87 References
88 ----------
89 ..  Torrents, J. and F. Ferraro (2015) Structural Cohesion:
90 Visualization and Heuristics for Fast Computation.
91 https://arxiv.org/pdf/1503.04476v1
92
93 ..  White, Douglas R., and Mark Newman (2001) A Fast Algorithm for
94 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
95 http://eclectic.ss.uci.edu/~drwhite/working.pdf
96
97 ..  Moody, J. and D. White (2003). Social cohesion and embeddedness:
98 A hierarchical conception of social groups.
99 American Sociological Review 68(1), 103--28.
100 http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf
101
102 """
103 # Dictionary with connectivity level (k) as keys and a list of
104 # sets of nodes that form a k-component as values
105 k_components = defaultdict(list)
106 # make a few functions local for speed
107 node_connectivity = local_node_connectivity
108 k_core = nx.k_core
109 core_number = nx.core_number
110 biconnected_components = nx.biconnected_components
111 density = nx.density
112 combinations = itertools.combinations
113 # Exact solution for k = {1,2}
114 # There is a linear time algorithm for triconnectivity, if we had an
115 # implementation available we could start from k = 4.
116 for component in nx.connected_components(G):
117 # isolated nodes have connectivity 0
118 comp = set(component)
119 if len(comp) > 1:
120 k_components.append(comp)
121 for bicomponent in nx.biconnected_components(G):
122 # avoid considering dyads as bicomponents
123 bicomp = set(bicomponent)
124 if len(bicomp) > 2:
125 k_components.append(bicomp)
126 # There is no k-component of k > maximum core number
127 # \kappa(G) <= \lambda(G) <= \delta(G)
128 g_cnumber = core_number(G)
129 max_core = max(g_cnumber.values())
130 for k in range(3, max_core + 1):
131 C = k_core(G, k, core_number=g_cnumber)
132 for nodes in biconnected_components(C):
133 # Build a subgraph SG induced by the nodes that are part of
134 # each biconnected component of the k-core subgraph C.
135 if len(nodes) < k:
136 continue
137 SG = G.subgraph(nodes)
138 # Build auxiliary graph
139 H = _AntiGraph()
141 for u, v in combinations(SG, 2):
142 K = node_connectivity(SG, u, v, cutoff=k)
143 if k > K:
145 for h_nodes in biconnected_components(H):
146 if len(h_nodes) <= k:
147 continue
148 SH = H.subgraph(h_nodes)
149 for Gc in _cliques_heuristic(SG, SH, k, min_density):
150 for k_nodes in biconnected_components(Gc):
151 Gk = nx.k_core(SG.subgraph(k_nodes), k)
152 if len(Gk) <= k:
153 continue
154 k_components[k].append(set(Gk))
155 return k_components
156
157
158 def _cliques_heuristic(G, H, k, min_density):
159 h_cnumber = nx.core_number(H)
160 for i, c_value in enumerate(sorted(set(h_cnumber.values()), reverse=True)):
161 cands = {n for n, c in h_cnumber.items() if c == c_value}
162 # Skip checking for overlap for the highest core value
163 if i == 0:
164 overlap = False
165 else:
166 overlap = set.intersection(
167 *[{x for x in H[n] if x not in cands} for n in cands]
168 )
169 if overlap and len(overlap) < k:
170 SH = H.subgraph(cands | overlap)
171 else:
172 SH = H.subgraph(cands)
173 sh_cnumber = nx.core_number(SH)
174 SG = nx.k_core(G.subgraph(SH), k)
175 while not (_same(sh_cnumber) and nx.density(SH) >= min_density):
176 # This subgraph must be writable => .copy()
177 SH = H.subgraph(SG).copy()
178 if len(SH) <= k:
179 break
180 sh_cnumber = nx.core_number(SH)
181 sh_deg = dict(SH.degree())
182 min_deg = min(sh_deg.values())
183 SH.remove_nodes_from(n for n, d in sh_deg.items() if d == min_deg)
184 SG = nx.k_core(G.subgraph(SH), k)
185 else:
186 yield SG
187
188
189 def _same(measure, tol=0):
190 vals = set(measure.values())
191 if (max(vals) - min(vals)) <= tol:
192 return True
193 return False
194
195
196 class _AntiGraph(nx.Graph):
197 """
198 Class for complement graphs.
199
200 The main goal is to be able to work with big and dense graphs with
201 a low memory foodprint.
202
203 In this class you add the edges that *do not exist* in the dense graph,
204 the report methods of the class return the neighbors, the edges and
205 the degree as if it was the dense graph. Thus it's possible to use
206 an instance of this class with some of NetworkX functions. In this
207 case we only use k-core, connected_components, and biconnected_components.
208 """
209
210 all_edge_dict = {"weight": 1}
211
212 def single_edge_dict(self):
213 return self.all_edge_dict
214
215 edge_attr_dict_factory = single_edge_dict
216
217 def __getitem__(self, n):
218 """Returns a dict of neighbors of node n in the dense graph.
219
220 Parameters
221 ----------
222 n : node
223 A node in the graph.
224
225 Returns
226 -------
227 adj_dict : dictionary
228 The adjacency dictionary for nodes connected to n.
229
230 """
231 all_edge_dict = self.all_edge_dict
232 return {
233 node: all_edge_dict for node in set(self._adj) - set(self._adj[n]) - {n}
234 }
235
236 def neighbors(self, n):
237 """Returns an iterator over all neighbors of node n in the
238 dense graph.
239 """
240 try:
241 return iter(set(self._adj) - set(self._adj[n]) - {n})
242 except KeyError as e:
243 raise NetworkXError(f"The node {n} is not in the graph.") from e
244
245 class AntiAtlasView(Mapping):
246 """An adjacency inner dict for AntiGraph"""
247
248 def __init__(self, graph, node):
249 self._graph = graph
250 self._atlas = graph._adj[node]
251 self._node = node
252
253 def __len__(self):
254 return len(self._graph) - len(self._atlas) - 1
255
256 def __iter__(self):
257 return (n for n in self._graph if n not in self._atlas and n != self._node)
258
259 def __getitem__(self, nbr):
260 nbrs = set(self._graph._adj) - set(self._atlas) - {self._node}
261 if nbr in nbrs:
262 return self._graph.all_edge_dict
263 raise KeyError(nbr)
264
266 """An adjacency outer dict for AntiGraph"""
267
268 def __init__(self, graph):
269 self._graph = graph
270 self._atlas = graph._adj
271
272 def __len__(self):
273 return len(self._atlas)
274
275 def __iter__(self):
276 return iter(self._graph)
277
278 def __getitem__(self, node):
279 if node not in self._graph:
280 raise KeyError(node)
281 return self._graph.AntiAtlasView(self._graph, node)
282
283 @property
286
287 def subgraph(self, nodes):
288 """This subgraph method returns a full AntiGraph. Not a View"""
289 nodes = set(nodes)
290 G = _AntiGraph()
292 for n in G:
293 Gnbrs = G.adjlist_inner_dict_factory()
294 G._adj[n] = Gnbrs
295 for nbr, d in self._adj[n].items():
296 if nbr in G._adj:
297 Gnbrs[nbr] = d
298 G._adj[nbr][n] = d
299 G.graph = self.graph
300 return G
301
302 class AntiDegreeView(nx.reportviews.DegreeView):
303 def __iter__(self):
304 all_nodes = set(self._succ)
305 for n in self._nodes:
306 nbrs = all_nodes - set(self._succ[n]) - {n}
307 yield (n, len(nbrs))
308
309 def __getitem__(self, n):
310 nbrs = set(self._succ) - set(self._succ[n]) - {n}
311 # AntiGraph is a ThinGraph so all edges have weight 1
312 return len(nbrs) + (n in nbrs)
313
314 @property
315 def degree(self):
316 """Returns an iterator for (node, degree) and degree for single node.
317
318 The node degree is the number of edges adjacent to the node.
319
320 Parameters
321 ----------
322 nbunch : iterable container, optional (default=all nodes)
323 A container of nodes. The container will be iterated
324 through once.
325
326 weight : string or None, optional (default=None)
327 The edge attribute that holds the numerical value used
328 as a weight. If None, then each edge has weight 1.
329 The degree is the sum of the edge weights adjacent to the node.
330
331 Returns
332 -------
333 deg:
334 Degree of the node, if a single node is passed as argument.
335 nd_iter : an iterator
336 The iterator returns two-tuples of (node, degree).
337
339 --------
340 degree
341
342 Examples
343 --------
344 >>> G = nx.path_graph(4)
345 >>> G.degree(0) # node 0 with degree 1
346 1
347 >>> list(G.degree([0, 1]))
348 [(0, 1), (1, 2)]
349
350 """
351 return self.AntiDegreeView(self)
352
354 """Returns an iterator of (node, adjacency set) tuples for all nodes
355 in the dense graph.
356
357 This is the fastest way to look at every edge.
358 For directed graphs, only outgoing adjacencies are included.
359
360 Returns
361 -------
362 adj_iter : iterator
363 An iterator of (node, adjacency set) for all nodes in
364 the graph.
365
366 """
367 for n in self._adj:
368 yield (n, set(self._adj) - set(self._adj[n]) - {n})