ioftools / networkxMiCe / networkxmaster / networkx / algorithms / community / quality.py @ 5cef0f13
History  View  Annotate  Download (9.63 KB)
1 
# quality.py  functions for measuring partitions of a graph


2 
#

3 
# Copyright 20152019 NetworkX developers.

4 
#

5 
# This file is part of NetworkX.

6 
#

7 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

8 
# information.

9 
"""Functions for measuring the quality of a partition (into

10 
communities).

11 

12 
"""

13 
from __future__ import division 
14  
15 
from functools import wraps 
16 
from itertools import product 
17  
18 
import networkx as nx 
19 
from networkx import NetworkXError 
20 
from networkx.utils import not_implemented_for 
21 
from networkx.algorithms.community.community_utils import is_partition 
22  
23 
__all__ = ['coverage', 'modularity', 'performance'] 
24  
25  
26 
class NotAPartition(NetworkXError): 
27 
"""Raised if a given collection is not a partition.

28 

29 
"""

30  
31 
def __init__(self, G, collection): 
32 
msg = '{} is not a valid partition of the graph {}'

33 
msg = msg.format(G, collection) 
34 
super(NotAPartition, self).__init__(msg) 
35  
36  
37 
def require_partition(func): 
38 
"""Decorator that raises an exception if a partition is not a valid

39 
partition of the nodes of a graph.

40 

41 
Raises :exc:`networkx.NetworkXError` if the partition is not valid.

42 

43 
This decorator should be used on functions whose first two arguments

44 
are a graph and a partition of the nodes of that graph (in that

45 
order)::

46 

47 
>>> @require_partition

48 
... def foo(G, partition):

49 
... print('partition is valid!')

50 
...

51 
>>> G = nx.complete_graph(5)

52 
>>> partition = [{0, 1}, {2, 3}, {4}]

53 
>>> foo(G, partition)

54 
partition is valid!

55 
>>> partition = [{0}, {2, 3}, {4}]

56 
>>> foo(G, partition) # doctest: +IGNORE_EXCEPTION_DETAIL

57 
Traceback (most recent call last):

58 
...

59 
NetworkXError: `partition` is not a valid partition of the nodes of G

60 
>>> partition = [{0, 1}, {1, 2, 3}, {4}]

61 
>>> foo(G, partition) # doctest: +IGNORE_EXCEPTION_DETAIL

62 
Traceback (most recent call last):

63 
...

64 
NetworkXError: `partition` is not a valid partition of the nodes of G

65 

66 
"""

67  
68 
@wraps(func)

69 
def new_func(*args, **kw): 
70 
# Here we assume that the first two arguments are (G, partition).

71 
if not is_partition(*args[:2]): 
72 
raise nx.NetworkXError('`partition` is not a valid partition of' 
73 
' the nodes of G')

74 
return func(*args, **kw)

75 
return new_func

76  
77  
78 
def intra_community_edges(G, partition): 
79 
"""Returns the number of intracommunity edges according to the given

80 
partition of the nodes of `G`.

81 

82 
`G` must be a NetworkX graph.

83 

84 
`partition` must be a partition of the nodes of `G`.

85 

86 
The "intracommunity edges" are those edges joining a pair of nodes

87 
in the same block of the partition.

88 

89 
"""

90 
return sum(G.subgraph(block).size() for block in partition) 
91  
92  
93 
def inter_community_edges(G, partition): 
94 
"""Returns the number of intercommunity edges according to the given

95 
partition of the nodes of `G`.

96 

97 
`G` must be a NetworkX graph.

98 

99 
`partition` must be a partition of the nodes of `G`.

100 

101 
The *intercommunity edges* are those edges joining a pair of nodes

102 
in different blocks of the partition.

103 

104 
Implementation note: this function creates an intermediate graph

105 
that may require the same amount of memory as required to store

106 
`G`.

107 

108 
"""

109 
# Alternate implementation that does not require constructing a new

110 
# graph object (but does require constructing an affiliation

111 
# dictionary):

112 
#

113 
# aff = dict(chain.from_iterable(((v, block) for v in block)

114 
# for block in partition))

115 
# return sum(1 for u, v in G.edges() if aff[u] != aff[v])

116 
#

117 
if G.is_directed():

118 
return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()

119 
else:

120 
return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()

121  
122  
123 
def inter_community_non_edges(G, partition): 
124 
"""Returns the number of intercommunity nonedges according to the

125 
given partition of the nodes of `G`.

126 

127 
`G` must be a NetworkX graph.

128 

129 
`partition` must be a partition of the nodes of `G`.

130 

131 
A *nonedge* is a pair of nodes (undirected if `G` is undirected)

132 
that are not adjacent in `G`. The *intercommunity nonedges* are

133 
those nonedges on a pair of nodes in different blocks of the

134 
partition.

135 

136 
Implementation note: this function creates two intermediate graphs,

137 
which may require up to twice the amount of memory as required to

138 
store `G`.

139 

140 
"""

141 
# Alternate implementation that does not require constructing two

142 
# new graph objects (but does require constructing an affiliation

143 
# dictionary):

144 
#

145 
# aff = dict(chain.from_iterable(((v, block) for v in block)

146 
# for block in partition))

147 
# return sum(1 for u, v in nx.non_edges(G) if aff[u] != aff[v])

148 
#

149 
return inter_community_edges(nx.complement(G), partition)

150  
151  
152 
@not_implemented_for('multigraph') 
153 
@require_partition

154 
def performance(G, partition): 
155 
"""Returns the performance of a partition.

156 

157 
The *performance* of a partition is the ratio of the number of

158 
intracommunity edges plus intercommunity nonedges with the total

159 
number of potential edges.

160 

161 
Parameters

162 


163 
G : NetworkX graph

164 
A simple graph (directed or undirected).

165 

166 
partition : sequence

167 

168 
Partition of the nodes of `G`, represented as a sequence of

169 
sets of nodes. Each block of the partition represents a

170 
community.

171 

172 
Returns

173 


174 
float

175 
The performance of the partition, as defined above.

176 

177 
Raises

178 


179 
NetworkXError

180 
If `partition` is not a valid partition of the nodes of `G`.

181 

182 
References

183 


184 
.. [1] Santo Fortunato.

185 
"Community Detection in Graphs".

186 
*Physical Reports*, Volume 486, Issue 35 pp. 75174

187 
<https://arxiv.org/abs/0906.0612>

188 

189 
"""

190 
# Compute the number of intracommunity edges and intercommunity

191 
# edges.

192 
intra_edges = intra_community_edges(G, partition) 
193 
inter_edges = inter_community_non_edges(G, partition) 
194 
# Compute the number of edges in the complete graph (directed or

195 
# undirected, as it depends on `G`) on `n` nodes.

196 
#

197 
# (If `G` is an undirected graph, we divide by two since we have

198 
# doublecounted each potential edge. We use integer division since

199 
# `total_pairs` is guaranteed to be even.)

200 
n = len(G)

201 
total_pairs = n * (n  1)

202 
if not G.is_directed(): 
203 
total_pairs //= 2

204 
return (intra_edges + inter_edges) / total_pairs

205  
206  
207 
@require_partition

208 
def coverage(G, partition): 
209 
"""Returns the coverage of a partition.

210 

211 
The *coverage* of a partition is the ratio of the number of

212 
intracommunity edges to the total number of edges in the graph.

213 

214 
Parameters

215 


216 
G : NetworkX graph

217 

218 
partition : sequence

219 
Partition of the nodes of `G`, represented as a sequence of

220 
sets of nodes. Each block of the partition represents a

221 
community.

222 

223 
Returns

224 


225 
float

226 
The coverage of the partition, as defined above.

227 

228 
Raises

229 


230 
NetworkXError

231 
If `partition` is not a valid partition of the nodes of `G`.

232 

233 
Notes

234 


235 
If `G` is a multigraph, the multiplicity of edges is counted.

236 

237 
References

238 


239 
.. [1] Santo Fortunato.

240 
"Community Detection in Graphs".

241 
*Physical Reports*, Volume 486, Issue 35 pp. 75174

242 
<https://arxiv.org/abs/0906.0612>

243 

244 
"""

245 
intra_edges = intra_community_edges(G, partition) 
246 
total_edges = G.number_of_edges() 
247 
return intra_edges / total_edges

248  
249  
250 
def modularity(G, communities, weight='weight'): 
251 
r"""Returns the modularity of the given partition of the graph.

252 

253 
Modularity is defined in [1]_ as

254 

255 
.. math::

256 

257 
Q = \frac{1}{2m} \sum_{ij} \left( A_{ij}  \frac{k_ik_j}{2m}\right)

258 
\delta(c_i,c_j)

259 

260 
where $m$ is the number of edges, $A$ is the adjacency matrix of

261 
`G`, $k_i$ is the degree of $i$ and $\delta(c_i, c_j)$

262 
is 1 if $i$ and $j$ are in the same community and 0 otherwise.

263 

264 
Parameters

265 


266 
G : NetworkX Graph

267 

268 
communities : list

269 
List of sets of nodes of `G` representing a partition of the

270 
nodes.

271 

272 
Returns

273 


274 
Q : float

275 
The modularity of the paritition.

276 

277 
Raises

278 


279 
NotAPartition

280 
If `communities` is not a partition of the nodes of `G`.

281 

282 
Examples

283 


284 
>>> G = nx.barbell_graph(3, 0)

285 
>>> nx.algorithms.community.modularity(G, [{0, 1, 2}, {3, 4, 5}])

286 
0.35714285714285704

287 

288 
References

289 


290 
.. [1] M. E. J. Newman *Networks: An Introduction*, page 224.

291 
Oxford University Press, 2011.

292 

293 
"""

294 
if not is_partition(G, communities): 
295 
raise NotAPartition(G, communities)

296  
297 
multigraph = G.is_multigraph() 
298 
directed = G.is_directed() 
299 
m = G.size(weight=weight) 
300 
if directed:

301 
out_degree = dict(G.out_degree(weight=weight))

302 
in_degree = dict(G.in_degree(weight=weight))

303 
norm = 1 / m

304 
else:

305 
out_degree = dict(G.degree(weight=weight))

306 
in_degree = out_degree 
307 
norm = 1 / (2 * m) 
308  
309 
def val(u, v): 
310 
try:

311 
if multigraph:

312 
w = sum(d.get(weight, 1) for k, d in G[u][v].items()) 
313 
else:

314 
w = G[u][v].get(weight, 1)

315 
except KeyError: 
316 
w = 0

317 
# Double count selfloops if the graph is undirected.

318 
if u == v and not directed: 
319 
w *= 2

320 
return w  in_degree[u] * out_degree[v] * norm

321  
322 
Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2)) 
323 
return Q * norm
