ioftools / networkxMiCe / networkxmaster / networkx / algorithms / cuts.py @ 5cef0f13
History  View  Annotate  Download (9.8 KB)
1 
# * coding: utf8 *


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 0821803158

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) 