## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / community / quality.py @ 5cef0f13

History | View | Annotate | Download (9.63 KB)

1 | 5cef0f13 | tiamilani | ```
# quality.py - functions for measuring partitions of a graph
``` |
---|---|---|---|

2 | ```
#
``` |
||

3 | ```
# Copyright 2015-2019 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 intra-community 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 "intra-community 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 inter-community 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 *inter-community 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 inter-community non-edges 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 *non-edge* is a pair of nodes (undirected if `G` is undirected)
``` |
||

132 | ```
that are not adjacent in `G`. The *inter-community non-edges* are
``` |
||

133 | ```
those non-edges 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 | ```
intra-community edges plus inter-community non-edges 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 3--5 pp. 75--174
``` |
||

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

188 | ```
``` |
||

189 | ```
"""
``` |
||

190 | ```
# Compute the number of intra-community edges and inter-community
``` |
||

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 | ```
# double-counted 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 | ```
intra-community 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 3--5 pp. 75--174
``` |
||

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 self-loops 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` |