Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 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