Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / cuts.py @ 5cef0f13

History | View | Annotate | Download (9.8 KB)

1
# -*- coding: utf-8 -*-
2
# cuts.py - functions for computing and evaluating cuts
3
#
4
# Copyright 2011 Ben Edwards <bedwards@cs.unm.edu>.
5
# Copyright 2011 Aric Hagberg <hagberg@lanl.gov>.
6
# Copyright 2015 NetworkX developers.
7
#
8
# This file is part of NetworkX.
9
#
10
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
11
# information.
12
"""Functions for finding and evaluating cuts in a graph.
13

14
"""
15
from __future__ import division
16

    
17
from itertools import chain
18

    
19
import networkx as nx
20

    
21
__all__ = ['boundary_expansion', 'conductance', 'cut_size', 'edge_expansion',
22
           'mixing_expansion', 'node_expansion', 'normalized_cut_size',
23
           'volume']
24

    
25

    
26
# TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION!
27

    
28
def cut_size(G, S, T=None, weight=None):
29
    """Returns the size of the cut between two sets of nodes.
30

31
    A *cut* is a partition of the nodes of a graph into two sets. The
32
    *cut size* is the sum of the weights of the edges "between" the two
33
    sets of nodes.
34

35
    Parameters
36
    ----------
37
    G : NetworkX graph
38

39
    S : sequence
40
        A sequence of nodes in `G`.
41

42
    T : sequence
43
        A sequence of nodes in `G`. If not specified, this is taken to
44
        be the set complement of `S`.
45

46
    weight : object
47
        Edge attribute key to use as weight. If not specified, edges
48
        have weight one.
49

50
    Returns
51
    -------
52
    number
53
        Total weight of all edges from nodes in set `S` to nodes in
54
        set `T` (and, in the case of directed graphs, all edges from
55
        nodes in `T` to nodes in `S`).
56

57
    Examples
58
    --------
59
    In the graph with two cliques joined by a single edges, the natural
60
    bipartition of the graph into two blocks, one for each clique,
61
    yields a cut of weight one::
62

63
        >>> G = nx.barbell_graph(3, 0)
64
        >>> S = {0, 1, 2}
65
        >>> T = {3, 4, 5}
66
        >>> nx.cut_size(G, S, T)
67
        1
68

69
    Each parallel edge in a multigraph is counted when determining the
70
    cut size::
71

72
        >>> G = nx.MultiGraph(['ab', 'ab'])
73
        >>> S = {'a'}
74
        >>> T = {'b'}
75
        >>> nx.cut_size(G, S, T)
76
        2
77

78
    Notes
79
    -----
80
    In a multigraph, the cut size is the total weight of edges including
81
    multiplicity.
82

83
    """
84
    edges = nx.edge_boundary(G, S, T, data=weight, default=1)
85
    if G.is_directed():
86
        edges = chain(edges, nx.edge_boundary(G, T, S, data=weight, default=1))
87
    return sum(weight for u, v, weight in edges)
88

    
89

    
90
def volume(G, S, weight=None):
91
    """Returns the volume of a set of nodes.
92

93
    The *volume* of a set *S* is the sum of the (out-)degrees of nodes
94
    in *S* (taking into account parallel edges in multigraphs). [1]
95

96
    Parameters
97
    ----------
98
    G : NetworkX graph
99

100
    S : sequence
101
        A sequence of nodes in `G`.
102

103
    weight : object
104
        Edge attribute key to use as weight. If not specified, edges
105
        have weight one.
106

107
    Returns
108
    -------
109
    number
110
        The volume of the set of nodes represented by `S` in the graph
111
        `G`.
112

113
    See also
114
    --------
115
    conductance
116
    cut_size
117
    edge_expansion
118
    edge_boundary
119
    normalized_cut_size
120

121
    References
122
    ----------
123
    .. [1] David Gleich.
124
           *Hierarchical Directed Spectral Graph Partitioning*.
125
           <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
126

127
    """
128
    degree = G.out_degree if G.is_directed() else G.degree
129
    return sum(d for v, d in degree(S, weight=weight))
130

    
131

    
132
def normalized_cut_size(G, S, T=None, weight=None):
133
    """Returns the normalized size of the cut between two sets of nodes.
134

135
    The *normalized cut size* is the cut size times the sum of the
136
    reciprocal sizes of the volumes of the two sets. [1]
137

138
    Parameters
139
    ----------
140
    G : NetworkX graph
141

142
    S : sequence
143
        A sequence of nodes in `G`.
144

145
    T : sequence
146
        A sequence of nodes in `G`.
147

148
    weight : object
149
        Edge attribute key to use as weight. If not specified, edges
150
        have weight one.
151

152
    Returns
153
    -------
154
    number
155
        The normalized cut size between the two sets `S` and `T`.
156

157
    Notes
158
    -----
159
    In a multigraph, the cut size is the total weight of edges including
160
    multiplicity.
161

162
    See also
163
    --------
164
    conductance
165
    cut_size
166
    edge_expansion
167
    volume
168

169
    References
170
    ----------
171
    .. [1] David Gleich.
172
           *Hierarchical Directed Spectral Graph Partitioning*.
173
           <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
174

175
    """
176
    if T is None:
177
        T = set(G) - set(S)
178
    num_cut_edges = cut_size(G, S, T=T, weight=weight)
179
    volume_S = volume(G, S, weight=weight)
180
    volume_T = volume(G, T, weight=weight)
181
    return num_cut_edges * ((1 / volume_S) + (1 / volume_T))
182

    
183

    
184
def conductance(G, S, T=None, weight=None):
185
    """Returns the conductance of two sets of nodes.
186

187
    The *conductance* is the quotient of the cut size and the smaller of
188
    the volumes of the two sets. [1]
189

190
    Parameters
191
    ----------
192
    G : NetworkX graph
193

194
    S : sequence
195
        A sequence of nodes in `G`.
196

197
    T : sequence
198
        A sequence of nodes in `G`.
199

200
    weight : object
201
        Edge attribute key to use as weight. If not specified, edges
202
        have weight one.
203

204
    Returns
205
    -------
206
    number
207
        The conductance between the two sets `S` and `T`.
208

209
    See also
210
    --------
211
    cut_size
212
    edge_expansion
213
    normalized_cut_size
214
    volume
215

216
    References
217
    ----------
218
    .. [1] David Gleich.
219
           *Hierarchical Directed Spectral Graph Partitioning*.
220
           <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>
221

222
    """
223
    if T is None:
224
        T = set(G) - set(S)
225
    num_cut_edges = cut_size(G, S, T, weight=weight)
226
    volume_S = volume(G, S, weight=weight)
227
    volume_T = volume(G, T, weight=weight)
228
    return num_cut_edges / min(volume_S, volume_T)
229

    
230

    
231
def edge_expansion(G, S, T=None, weight=None):
232
    """Returns the edge expansion between two node sets.
233

234
    The *edge expansion* is the quotient of the cut size and the smaller
235
    of the cardinalities of the two sets. [1]
236

237
    Parameters
238
    ----------
239
    G : NetworkX graph
240

241
    S : sequence
242
        A sequence of nodes in `G`.
243

244
    T : sequence
245
        A sequence of nodes in `G`.
246

247
    weight : object
248
        Edge attribute key to use as weight. If not specified, edges
249
        have weight one.
250

251
    Returns
252
    -------
253
    number
254
        The edge expansion between the two sets `S` and `T`.
255

256
    See also
257
    --------
258
    boundary_expansion
259
    mixing_expansion
260
    node_expansion
261

262
    References
263
    ----------
264
    .. [1] Fan Chung.
265
           *Spectral Graph Theory*.
266
           (CBMS Regional Conference Series in Mathematics, No. 92),
267
           American Mathematical Society, 1997, ISBN 0-8218-0315-8
268
           <http://www.math.ucsd.edu/~fan/research/revised.html>
269

270
    """
271
    if T is None:
272
        T = set(G) - set(S)
273
    num_cut_edges = cut_size(G, S, T=T, weight=weight)
274
    return num_cut_edges / min(len(S), len(T))
275

    
276

    
277
def mixing_expansion(G, S, T=None, weight=None):
278
    """Returns the mixing expansion between two node sets.
279

280
    The *mixing expansion* is the quotient of the cut size and twice the
281
    number of edges in the graph. [1]
282

283
    Parameters
284
    ----------
285
    G : NetworkX graph
286

287
    S : sequence
288
        A sequence of nodes in `G`.
289

290
    T : sequence
291
        A sequence of nodes in `G`.
292

293
    weight : object
294
        Edge attribute key to use as weight. If not specified, edges
295
        have weight one.
296

297
    Returns
298
    -------
299
    number
300
        The mixing expansion between the two sets `S` and `T`.
301

302
    See also
303
    --------
304
    boundary_expansion
305
    edge_expansion
306
    node_expansion
307

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>
315

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)
320

    
321

    
322
# TODO What is the generalization to two arguments, S and T? Does the
323
# denominator become `min(len(S), len(T))`?
324
def node_expansion(G, S):
325
    """Returns the node expansion of the set `S`.
326

327
    The *node expansion* is the quotient of the size of the node
328
    boundary of *S* and the cardinality of *S*. [1]
329

330
    Parameters
331
    ----------
332
    G : NetworkX graph
333

334
    S : sequence
335
        A sequence of nodes in `G`.
336

337
    Returns
338
    -------
339
    number
340
        The node expansion of the set `S`.
341

342
    See also
343
    --------
344
    boundary_expansion
345
    edge_expansion
346
    mixing_expansion
347

348
    References
349
    ----------
350
    .. [1] Vadhan, Salil P.
351
           "Pseudorandomness."
352
           *Foundations and Trends
353
           in Theoretical Computer Science* 7.1–3 (2011): 1–336.
354
           <https://doi.org/10.1561/0400000010>
355

356
    """
357
    neighborhood = set(chain.from_iterable(G.neighbors(v) for v in S))
358
    return len(neighborhood) / len(S)
359

    
360

    
361
# TODO What is the generalization to two arguments, S and T? Does the
362
# denominator become `min(len(S), len(T))`?
363
def boundary_expansion(G, S):
364
    """Returns the boundary expansion of the set `S`.
365

366
    The *boundary expansion* is the quotient of the size of the edge
367
    boundary and the cardinality of *S*. [1]
368

369
    Parameters
370
    ----------
371
    G : NetworkX graph
372

373
    S : sequence
374
        A sequence of nodes in `G`.
375

376
    Returns
377
    -------
378
    number
379
        The boundary expansion of the set `S`.
380

381
    See also
382
    --------
383
    edge_expansion
384
    mixing_expansion
385
    node_expansion
386

387
    References
388
    ----------
389
    .. [1] Vadhan, Salil P.
390
           "Pseudorandomness."
391
           *Foundations and Trends in Theoretical Computer Science*
392
           7.1–3 (2011): 1–336.
393
           <https://doi.org/10.1561/0400000010>
394

395
    """
396
    return len(nx.node_boundary(G, S)) / len(S)