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"""Functions for finding and evaluating cuts in a graph."""
3from itertools import chain
5import networkx as nx
7__all__ = [
8 "boundary_expansion",
9 "conductance",
10 "cut_size",
11 "edge_expansion",
12 "mixing_expansion",
13 "node_expansion",
14 "normalized_cut_size",
15 "volume",
16]
19# TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION!
22@nx._dispatchable(edge_attrs="weight")
23def cut_size(G, S, T=None, weight=None):
24 """Returns the size of the cut between two sets of nodes.
26 A *cut* is a partition of the nodes of a graph into two sets. The
27 *cut size* is the sum of the weights of the edges "between" the two
28 sets of nodes.
30 Parameters
31 ----------
32 G : NetworkX graph
34 S : collection
35 A collection of nodes in `G`.
37 T : collection
38 A collection of nodes in `G`. If not specified, this is taken to
39 be the set complement of `S`.
41 weight : object
42 Edge attribute key to use as weight. If not specified, edges
43 have weight one.
45 Returns
46 -------
47 number
48 Total weight of all edges from nodes in set `S` to nodes in
49 set `T` (and, in the case of directed graphs, all edges from
50 nodes in `T` to nodes in `S`).
52 Examples
53 --------
54 In the graph with two cliques joined by a single edges, the natural
55 bipartition of the graph into two blocks, one for each clique,
56 yields a cut of weight one::
58 >>> G = nx.barbell_graph(3, 0)
59 >>> S = {0, 1, 2}
60 >>> T = {3, 4, 5}
61 >>> nx.cut_size(G, S, T)
62 1
64 Each parallel edge in a multigraph is counted when determining the
65 cut size::
67 >>> G = nx.MultiGraph(["ab", "ab"])
68 >>> S = {"a"}
69 >>> T = {"b"}
70 >>> nx.cut_size(G, S, T)
71 2
73 Notes
74 -----
75 In a multigraph, the cut size is the total weight of edges including
76 multiplicity.
78 """
79 edges = nx.edge_boundary(G, S, T, data=weight, default=1)
80 if G.is_directed():
81 edges = chain(edges, nx.edge_boundary(G, T, S, data=weight, default=1))
82 return sum(weight for u, v, weight in edges)
85@nx._dispatchable(edge_attrs="weight")
86def volume(G, S, weight=None):
87 """Returns the volume of a set of nodes.
89 The *volume* of a set *S* is the sum of the (out-)degrees of nodes
90 in *S* (taking into account parallel edges in multigraphs). [1]
92 Parameters
93 ----------
94 G : NetworkX graph
96 S : collection
97 A collection of nodes in `G`.
99 weight : object
100 Edge attribute key to use as weight. If not specified, edges
101 have weight one.
103 Returns
104 -------
105 number
106 The volume of the set of nodes represented by `S` in the graph
107 `G`.
109 See also
110 --------
111 conductance
112 cut_size
113 edge_expansion
114 edge_boundary
115 normalized_cut_size
117 References
118 ----------
119 .. [1] David Gleich.
120 *Hierarchical Directed Spectral Graph Partitioning*.
121 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
123 """
124 degree = G.out_degree if G.is_directed() else G.degree
125 return sum(d for v, d in degree(S, weight=weight))
128@nx._dispatchable(edge_attrs="weight")
129def normalized_cut_size(G, S, T=None, weight=None):
130 """Returns the normalized size of the cut between two sets of nodes.
132 The *normalized cut size* is the cut size times the sum of the
133 reciprocal sizes of the volumes of the two sets. [1]
135 Parameters
136 ----------
137 G : NetworkX graph
139 S : collection
140 A collection of nodes in `G`.
142 T : collection
143 A collection of nodes in `G`.
145 weight : object
146 Edge attribute key to use as weight. If not specified, edges
147 have weight one.
149 Returns
150 -------
151 number
152 The normalized cut size between the two sets `S` and `T`.
154 Notes
155 -----
156 In a multigraph, the cut size is the total weight of edges including
157 multiplicity.
159 See also
160 --------
161 conductance
162 cut_size
163 edge_expansion
164 volume
166 References
167 ----------
168 .. [1] David Gleich.
169 *Hierarchical Directed Spectral Graph Partitioning*.
170 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
172 """
173 if T is None:
174 T = set(G) - set(S)
175 num_cut_edges = cut_size(G, S, T=T, weight=weight)
176 volume_S = volume(G, S, weight=weight)
177 volume_T = volume(G, T, weight=weight)
178 return num_cut_edges * ((1 / volume_S) + (1 / volume_T))
181@nx._dispatchable(edge_attrs="weight")
182def conductance(G, S, T=None, weight=None):
183 """Returns the conductance of two sets of nodes.
185 The *conductance* is the quotient of the cut size and the smaller of
186 the volumes of the two sets. [1]
188 Parameters
189 ----------
190 G : NetworkX graph
192 S : collection
193 A collection of nodes in `G`.
195 T : collection
196 A collection of nodes in `G`.
198 weight : object
199 Edge attribute key to use as weight. If not specified, edges
200 have weight one.
202 Returns
203 -------
204 number
205 The conductance between the two sets `S` and `T`.
207 See also
208 --------
209 cut_size
210 edge_expansion
211 normalized_cut_size
212 volume
214 References
215 ----------
216 .. [1] David Gleich.
217 *Hierarchical Directed Spectral Graph Partitioning*.
218 <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
220 """
221 if T is None:
222 T = set(G) - set(S)
223 num_cut_edges = cut_size(G, S, T, weight=weight)
224 volume_S = volume(G, S, weight=weight)
225 volume_T = volume(G, T, weight=weight)
226 return num_cut_edges / min(volume_S, volume_T)
229@nx._dispatchable(edge_attrs="weight")
230def edge_expansion(G, S, T=None, weight=None):
231 """Returns the edge expansion between two node sets.
233 The *edge expansion* is the quotient of the cut size and the smaller
234 of the cardinalities of the two sets. [1]
236 Parameters
237 ----------
238 G : NetworkX graph
240 S : collection
241 A collection of nodes in `G`.
243 T : collection
244 A collection of nodes in `G`.
246 weight : object
247 Edge attribute key to use as weight. If not specified, edges
248 have weight one.
250 Returns
251 -------
252 number
253 The edge expansion between the two sets `S` and `T`.
255 See also
256 --------
257 boundary_expansion
258 mixing_expansion
259 node_expansion
261 References
262 ----------
263 .. [1] Fan Chung.
264 *Spectral Graph Theory*.
265 (CBMS Regional Conference Series in Mathematics, No. 92),
266 American Mathematical Society, 1997, ISBN 0-8218-0315-8
267 <http://www.math.ucsd.edu/~fan/research/revised.html>
269 """
270 if T is None:
271 T = set(G) - set(S)
272 num_cut_edges = cut_size(G, S, T=T, weight=weight)
273 return num_cut_edges / min(len(S), len(T))
276@nx._dispatchable(edge_attrs="weight")
277def mixing_expansion(G, S, T=None, weight=None):
278 """Returns the mixing expansion between two node sets.
280 The *mixing expansion* is the quotient of the cut size and twice the
281 number of edges in the graph. [1]
283 Parameters
284 ----------
285 G : NetworkX graph
287 S : collection
288 A collection of nodes in `G`.
290 T : collection
291 A collection of nodes in `G`.
293 weight : object
294 Edge attribute key to use as weight. If not specified, edges
295 have weight one.
297 Returns
298 -------
299 number
300 The mixing expansion between the two sets `S` and `T`.
302 See also
303 --------
304 boundary_expansion
305 edge_expansion
306 node_expansion
308 References
309 ----------
310 .. [1] Vadhan, Salil P.
311 "Pseudorandomness."
312 *Foundations and Trends
313 in Theoretical Computer Science* 7.1–3 (2011): 1–336.
314 <https://doi.org/10.1561/0400000010>
316 """
317 num_cut_edges = cut_size(G, S, T=T, weight=weight)
318 num_total_edges = G.number_of_edges()
319 return num_cut_edges / (2 * num_total_edges)
322# TODO What is the generalization to two arguments, S and T? Does the
323# denominator become `min(len(S), len(T))`?
324@nx._dispatchable
325def node_expansion(G, S):
326 """Returns the node expansion of the set `S`.
328 The *node expansion* is the quotient of the size of the node
329 boundary of *S* and the cardinality of *S*. [1]
331 Parameters
332 ----------
333 G : NetworkX graph
335 S : collection
336 A collection of nodes in `G`.
338 Returns
339 -------
340 number
341 The node expansion of the set `S`.
343 See also
344 --------
345 boundary_expansion
346 edge_expansion
347 mixing_expansion
349 References
350 ----------
351 .. [1] Vadhan, Salil P.
352 "Pseudorandomness."
353 *Foundations and Trends
354 in Theoretical Computer Science* 7.1–3 (2011): 1–336.
355 <https://doi.org/10.1561/0400000010>
357 """
358 neighborhood = set(chain.from_iterable(G.neighbors(v) for v in S))
359 return len(neighborhood) / len(S)
362@nx._dispatchable
363def boundary_expansion(G, S):
364 """Returns the boundary expansion of the set `S`.
366 The *boundary expansion* of a set `S` is the ratio between the size of its
367 node boundary and the cardinality of the set itself [1]_ .
369 Parameters
370 ----------
371 G : NetworkX graph
372 The input graph.
374 S : collection
375 A collection of nodes in `G`.
377 Returns
378 -------
379 number
380 The boundary expansion ratio: size of node boundary / size of `S`.
382 Examples
383 --------
384 The node boundary is {2, 3} (size 2), divided by ``|S|=2``:
386 >>> G = nx.cycle_graph(4)
387 >>> S = {0, 1}
388 >>> nx.boundary_expansion(G, S)
389 1.0
391 For disconnected sets, e.g. here where the node boundary is ``{1, 3, 5}``:
393 >>> G = nx.cycle_graph(6)
394 >>> S = {0, 2, 4}
395 >>> nx.boundary_expansion(G, S)
396 1.0
398 See also
399 --------
400 :func:`~networkx.algorithms.boundary.node_boundary`
401 edge_expansion
402 mixing_expansion
403 node_expansion
405 Notes
406 -----
407 The node boundary is defined as all nodes not in `S` that are adjacent to
408 nodes in `S`.
410 References
411 ----------
412 .. [1] Vadhan, Salil P.
413 "Pseudorandomness." *Foundations and Trends in Theoretical Computer Science*
414 7.1–3 (2011): 1–336. <https://doi.org/10.1561/0400000010>
415 """
416 return len(nx.node_boundary(G, S)) / len(S)