We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
inter_community_non_edges ignore directionality
Hi,

I think the function:

nx.algorithms.community.quality.inter_community_non_edges()

does not work properly for directed graph. It always return the non-edge of a undirected graph, basically halving the number of edges. This mean that the performance function (nx.algorithms.community.performance) will never by higher than 50% for a directed graph.

I'm using version '2.0.dev_20170801111157', python 3.5.1

Best,

Nicolas 

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `networkx/algorithms/community/quality.py`
Content:
```
1 # quality.py - functions for measuring partitions of a graph
2 #
3 # Copyright 2015-2017 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     return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()
118 
119 
120 def inter_community_non_edges(G, partition):
121     """Returns the number of inter-community non-edges according to the
122     given partition of the nodes of `G`.
123 
124     `G` must be a NetworkX graph.
125 
126     `partition` must be a partition of the nodes of `G`.
127 
128     A *non-edge* is a pair of nodes (undirected if `G` is undirected)
129     that are not adjacent in `G`. The *inter-community non-edges* are
130     those non-edges on a pair of nodes in different blocks of the
131     partition.
132 
133     Implementation note: this function creates two intermediate graphs,
134     which may require up to twice the amount of memory as required to
135     store `G`.
136 
137     """
138     # Alternate implementation that does not require constructing two
139     # new graph objects (but does require constructing an affiliation
140     # dictionary):
141     #
142     #     aff = dict(chain.from_iterable(((v, block) for v in block)
143     #                                    for block in partition))
144     #     return sum(1 for u, v in nx.non_edges(G) if aff[u] != aff[v])
145     #
146     return inter_community_edges(nx.complement(G), partition)
147 
148 
149 @not_implemented_for('multigraph')
150 @require_partition
151 def performance(G, partition):
152     """Returns the performance of a partition.
153 
154     The *performance* of a partition is the ratio of the number of
155     intra-community edges plus inter-community non-edges with the total
156     number of potential edges.
157 
158     Parameters
159     ----------
160     G : NetworkX graph
161         A simple graph (directed or undirected).
162 
163     partition : sequence
164 
165         Partition of the nodes of `G`, represented as a sequence of
166         sets of nodes. Each block of the partition represents a
167         community.
168 
169     Returns
170     -------
171     float
172         The performance of the partition, as defined above.
173 
174     Raises
175     ------
176     NetworkXError
177         If `partition` is not a valid partition of the nodes of `G`.
178 
179     References
180     ----------
181     .. [1] Santo Fortunato.
182            "Community Detection in Graphs".
183            *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174
184            <https://arxiv.org/abs/0906.0612>
185 
186     """
187     # Compute the number of intra-community edges and inter-community
188     # edges.
189     intra_edges = intra_community_edges(G, partition)
190     inter_edges = inter_community_non_edges(G, partition)
191     # Compute the number of edges in the complete graph (directed or
192     # undirected, as it depends on `G`) on `n` nodes.
193     #
194     # (If `G` is an undirected graph, we divide by two since we have
195     # double-counted each potential edge. We use integer division since
196     # `total_pairs` is guaranteed to be even.)
197     n = len(G)
198     total_pairs = n * (n - 1)
199     if not G.is_directed():
200         total_pairs //= 2
201     return (intra_edges + inter_edges) / total_pairs
202 
203 
204 @require_partition
205 def coverage(G, partition):
206     """Returns the coverage of a partition.
207 
208     The *coverage* of a partition is the ratio of the number of
209     intra-community edges to the total number of edges in the graph.
210 
211     Parameters
212     ----------
213     G : NetworkX graph
214 
215     partition : sequence
216         Partition of the nodes of `G`, represented as a sequence of
217         sets of nodes. Each block of the partition represents a
218         community.
219 
220     Returns
221     -------
222     float
223         The coverage of the partition, as defined above.
224 
225     Raises
226     ------
227     NetworkXError
228         If `partition` is not a valid partition of the nodes of `G`.
229 
230     Notes
231     -----
232     If `G` is a multigraph, the multiplicity of edges is counted.
233 
234     References
235     ----------
236     .. [1] Santo Fortunato.
237            "Community Detection in Graphs".
238            *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174
239            <https://arxiv.org/abs/0906.0612>
240 
241     """
242     intra_edges = intra_community_edges(G, partition)
243     total_edges = G.number_of_edges()
244     return intra_edges / total_edges
245 
246 
247 def modularity(G, communities, weight='weight'):
248     r"""Returns the modularity of the given partition of the graph.
249 
250     Modularity is defined in [1]_ as
251 
252     .. math::
253 
254         Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right)
255             \delta(c_i,c_j)
256 
257     where $m$ is the number of edges, $A$ is the adjacency matrix of
258     `G`, $k_i$ is the degree of $i$ and $\delta(c_i, c_j)$
259     is 1 if $i$ and $j$ are in the same community and 0 otherwise.
260 
261     Parameters
262     ----------
263     G : NetworkX Graph
264 
265     communities : list
266         List of sets of nodes of `G` representing a partition of the
267         nodes.
268 
269     Returns
270     -------
271     Q : float
272         The modularity of the paritition.
273 
274     Raises
275     ------
276     NotAPartition
277         If `communities` is not a partition of the nodes of `G`.
278 
279     Examples
280     --------
281     >>> G = nx.barbell_graph(3, 0)
282     >>> nx.algorithms.community.modularity(G, [{0, 1, 2}, {3, 4, 5}])
283     0.35714285714285704
284 
285     References
286     ----------
287     .. [1] M. E. J. Newman *Networks: An Introduction*, page 224.
288        Oxford University Press, 2011.
289 
290     """
291     if not is_partition(G, communities):
292         raise NotAPartition(G, communities)
293 
294     multigraph = G.is_multigraph()
295     directed = G.is_directed()
296     m = G.size(weight=weight)
297     if directed:
298         out_degree = dict(G.out_degree(weight=weight))
299         in_degree = dict(G.in_degree(weight=weight))
300         norm = 1 / m
301     else:
302         out_degree = dict(G.degree(weight=weight))
303         in_degree = out_degree
304         norm = 1 / (2 * m)
305 
306     def val(u, v):
307         try:
308             if multigraph:
309                 w = sum(d.get(weight, 1) for k, d in G[u][v].items())
310             else:
311                 w = G[u][v].get(weight, 1)
312         except KeyError:
313             w = 0
314         # Double count self-loops if the graph is undirected.
315         if u == v and not directed:
316             w *= 2
317         return w - in_degree[u] * out_degree[v] * norm
318 
319     Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))
320     return Q * norm
321
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/networkx/algorithms/community/quality.py b/networkx/algorithms/community/quality.py
--- a/networkx/algorithms/community/quality.py
+++ b/networkx/algorithms/community/quality.py
@@ -114,7 +114,10 @@
     #                                    for block in partition))
     #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])
     #
-    return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()
+    if G.is_directed():
+        return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()
+    else:
+        return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()
 
 
 def inter_community_non_edges(G, partition):

{"golden_diff": "diff --git a/networkx/algorithms/community/quality.py b/networkx/algorithms/community/quality.py\n--- a/networkx/algorithms/community/quality.py\n+++ b/networkx/algorithms/community/quality.py\n@@ -114,7 +114,10 @@\n     #                                    for block in partition))\n     #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])\n     #\n-    return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()\n+    if G.is_directed():\n+        return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()\n+    else:\n+        return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()\n \n \n def inter_community_non_edges(G, partition):\n", "issue": "inter_community_non_edges ignore directionality\nHi,\r\n\r\nI think the function:\r\n\r\nnx.algorithms.community.quality.inter_community_non_edges()\r\n\r\ndoes not work properly for directed graph. It always return the non-edge of a undirected graph, basically halving the number of edges. This mean that the performance function (nx.algorithms.community.performance) will never by higher than 50% for a directed graph.\r\n\r\nI'm using version '2.0.dev_20170801111157', python 3.5.1\r\n\r\nBest,\r\n\r\nNicolas \n", "before_files": [{"content": "# quality.py - functions for measuring partitions of a graph\n#\n# Copyright 2015-2017 NetworkX developers.\n#\n# This file is part of NetworkX.\n#\n# NetworkX is distributed under a BSD license; see LICENSE.txt for more\n# information.\n\"\"\"Functions for measuring the quality of a partition (into\ncommunities).\n\n\"\"\"\nfrom __future__ import division\n\nfrom functools import wraps\nfrom itertools import product\n\nimport networkx as nx\nfrom networkx import NetworkXError\nfrom networkx.utils import not_implemented_for\nfrom networkx.algorithms.community.community_utils import is_partition\n\n__all__ = ['coverage', 'modularity', 'performance']\n\n\nclass NotAPartition(NetworkXError):\n    \"\"\"Raised if a given collection is not a partition.\n\n    \"\"\"\n\n    def __init__(self, G, collection):\n        msg = '{} is not a valid partition of the graph {}'\n        msg = msg.format(G, collection)\n        super(NotAPartition, self).__init__(msg)\n\n\ndef require_partition(func):\n    \"\"\"Decorator that raises an exception if a partition is not a valid\n    partition of the nodes of a graph.\n\n    Raises :exc:`networkx.NetworkXError` if the partition is not valid.\n\n    This decorator should be used on functions whose first two arguments\n    are a graph and a partition of the nodes of that graph (in that\n    order)::\n\n        >>> @require_partition\n        ... def foo(G, partition):\n        ...     print('partition is valid!')\n        ...\n        >>> G = nx.complete_graph(5)\n        >>> partition = [{0, 1}, {2, 3}, {4}]\n        >>> foo(G, partition)\n        partition is valid!\n        >>> partition = [{0}, {2, 3}, {4}]\n        >>> foo(G, partition)  # doctest: +IGNORE_EXCEPTION_DETAIL\n        Traceback (most recent call last):\n          ...\n        NetworkXError: `partition` is not a valid partition of the nodes of G\n        >>> partition = [{0, 1}, {1, 2, 3}, {4}]\n        >>> foo(G, partition)  # doctest: +IGNORE_EXCEPTION_DETAIL\n        Traceback (most recent call last):\n          ...\n        NetworkXError: `partition` is not a valid partition of the nodes of G\n\n    \"\"\"\n\n    @wraps(func)\n    def new_func(*args, **kw):\n        # Here we assume that the first two arguments are (G, partition).\n        if not is_partition(*args[:2]):\n            raise nx.NetworkXError('`partition` is not a valid partition of'\n                                   ' the nodes of G')\n        return func(*args, **kw)\n    return new_func\n\n\ndef intra_community_edges(G, partition):\n    \"\"\"Returns the number of intra-community edges according to the given\n    partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    The \"intra-community edges\" are those edges joining a pair of nodes\n    in the same block of the partition.\n\n    \"\"\"\n    return sum(G.subgraph(block).size() for block in partition)\n\n\ndef inter_community_edges(G, partition):\n    \"\"\"Returns the number of inter-community edges according to the given\n    partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    The *inter-community edges* are those edges joining a pair of nodes\n    in different blocks of the partition.\n\n    Implementation note: this function creates an intermediate graph\n    that may require the same amount of memory as required to store\n    `G`.\n\n    \"\"\"\n    # Alternate implementation that does not require constructing a new\n    # graph object (but does require constructing an affiliation\n    # dictionary):\n    #\n    #     aff = dict(chain.from_iterable(((v, block) for v in block)\n    #                                    for block in partition))\n    #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])\n    #\n    return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()\n\n\ndef inter_community_non_edges(G, partition):\n    \"\"\"Returns the number of inter-community non-edges according to the\n    given partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    A *non-edge* is a pair of nodes (undirected if `G` is undirected)\n    that are not adjacent in `G`. The *inter-community non-edges* are\n    those non-edges on a pair of nodes in different blocks of the\n    partition.\n\n    Implementation note: this function creates two intermediate graphs,\n    which may require up to twice the amount of memory as required to\n    store `G`.\n\n    \"\"\"\n    # Alternate implementation that does not require constructing two\n    # new graph objects (but does require constructing an affiliation\n    # dictionary):\n    #\n    #     aff = dict(chain.from_iterable(((v, block) for v in block)\n    #                                    for block in partition))\n    #     return sum(1 for u, v in nx.non_edges(G) if aff[u] != aff[v])\n    #\n    return inter_community_edges(nx.complement(G), partition)\n\n\n@not_implemented_for('multigraph')\n@require_partition\ndef performance(G, partition):\n    \"\"\"Returns the performance of a partition.\n\n    The *performance* of a partition is the ratio of the number of\n    intra-community edges plus inter-community non-edges with the total\n    number of potential edges.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        A simple graph (directed or undirected).\n\n    partition : sequence\n\n        Partition of the nodes of `G`, represented as a sequence of\n        sets of nodes. Each block of the partition represents a\n        community.\n\n    Returns\n    -------\n    float\n        The performance of the partition, as defined above.\n\n    Raises\n    ------\n    NetworkXError\n        If `partition` is not a valid partition of the nodes of `G`.\n\n    References\n    ----------\n    .. [1] Santo Fortunato.\n           \"Community Detection in Graphs\".\n           *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174\n           <https://arxiv.org/abs/0906.0612>\n\n    \"\"\"\n    # Compute the number of intra-community edges and inter-community\n    # edges.\n    intra_edges = intra_community_edges(G, partition)\n    inter_edges = inter_community_non_edges(G, partition)\n    # Compute the number of edges in the complete graph (directed or\n    # undirected, as it depends on `G`) on `n` nodes.\n    #\n    # (If `G` is an undirected graph, we divide by two since we have\n    # double-counted each potential edge. We use integer division since\n    # `total_pairs` is guaranteed to be even.)\n    n = len(G)\n    total_pairs = n * (n - 1)\n    if not G.is_directed():\n        total_pairs //= 2\n    return (intra_edges + inter_edges) / total_pairs\n\n\n@require_partition\ndef coverage(G, partition):\n    \"\"\"Returns the coverage of a partition.\n\n    The *coverage* of a partition is the ratio of the number of\n    intra-community edges to the total number of edges in the graph.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    partition : sequence\n        Partition of the nodes of `G`, represented as a sequence of\n        sets of nodes. Each block of the partition represents a\n        community.\n\n    Returns\n    -------\n    float\n        The coverage of the partition, as defined above.\n\n    Raises\n    ------\n    NetworkXError\n        If `partition` is not a valid partition of the nodes of `G`.\n\n    Notes\n    -----\n    If `G` is a multigraph, the multiplicity of edges is counted.\n\n    References\n    ----------\n    .. [1] Santo Fortunato.\n           \"Community Detection in Graphs\".\n           *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174\n           <https://arxiv.org/abs/0906.0612>\n\n    \"\"\"\n    intra_edges = intra_community_edges(G, partition)\n    total_edges = G.number_of_edges()\n    return intra_edges / total_edges\n\n\ndef modularity(G, communities, weight='weight'):\n    r\"\"\"Returns the modularity of the given partition of the graph.\n\n    Modularity is defined in [1]_ as\n\n    .. math::\n\n        Q = \\frac{1}{2m} \\sum_{ij} \\left( A_{ij} - \\frac{k_ik_j}{2m}\\right)\n            \\delta(c_i,c_j)\n\n    where $m$ is the number of edges, $A$ is the adjacency matrix of\n    `G`, $k_i$ is the degree of $i$ and $\\delta(c_i, c_j)$\n    is 1 if $i$ and $j$ are in the same community and 0 otherwise.\n\n    Parameters\n    ----------\n    G : NetworkX Graph\n\n    communities : list\n        List of sets of nodes of `G` representing a partition of the\n        nodes.\n\n    Returns\n    -------\n    Q : float\n        The modularity of the paritition.\n\n    Raises\n    ------\n    NotAPartition\n        If `communities` is not a partition of the nodes of `G`.\n\n    Examples\n    --------\n    >>> G = nx.barbell_graph(3, 0)\n    >>> nx.algorithms.community.modularity(G, [{0, 1, 2}, {3, 4, 5}])\n    0.35714285714285704\n\n    References\n    ----------\n    .. [1] M. E. J. Newman *Networks: An Introduction*, page 224.\n       Oxford University Press, 2011.\n\n    \"\"\"\n    if not is_partition(G, communities):\n        raise NotAPartition(G, communities)\n\n    multigraph = G.is_multigraph()\n    directed = G.is_directed()\n    m = G.size(weight=weight)\n    if directed:\n        out_degree = dict(G.out_degree(weight=weight))\n        in_degree = dict(G.in_degree(weight=weight))\n        norm = 1 / m\n    else:\n        out_degree = dict(G.degree(weight=weight))\n        in_degree = out_degree\n        norm = 1 / (2 * m)\n\n    def val(u, v):\n        try:\n            if multigraph:\n                w = sum(d.get(weight, 1) for k, d in G[u][v].items())\n            else:\n                w = G[u][v].get(weight, 1)\n        except KeyError:\n            w = 0\n        # Double count self-loops if the graph is undirected.\n        if u == v and not directed:\n            w *= 2\n        return w - in_degree[u] * out_degree[v] * norm\n\n    Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))\n    return Q * norm\n", "path": "networkx/algorithms/community/quality.py"}], "after_files": [{"content": "# quality.py - functions for measuring partitions of a graph\n#\n# Copyright 2015-2017 NetworkX developers.\n#\n# This file is part of NetworkX.\n#\n# NetworkX is distributed under a BSD license; see LICENSE.txt for more\n# information.\n\"\"\"Functions for measuring the quality of a partition (into\ncommunities).\n\n\"\"\"\nfrom __future__ import division\n\nfrom functools import wraps\nfrom itertools import product\n\nimport networkx as nx\nfrom networkx import NetworkXError\nfrom networkx.utils import not_implemented_for\nfrom networkx.algorithms.community.community_utils import is_partition\n\n__all__ = ['coverage', 'modularity', 'performance']\n\n\nclass NotAPartition(NetworkXError):\n    \"\"\"Raised if a given collection is not a partition.\n\n    \"\"\"\n\n    def __init__(self, G, collection):\n        msg = '{} is not a valid partition of the graph {}'\n        msg = msg.format(G, collection)\n        super(NotAPartition, self).__init__(msg)\n\n\ndef require_partition(func):\n    \"\"\"Decorator that raises an exception if a partition is not a valid\n    partition of the nodes of a graph.\n\n    Raises :exc:`networkx.NetworkXError` if the partition is not valid.\n\n    This decorator should be used on functions whose first two arguments\n    are a graph and a partition of the nodes of that graph (in that\n    order)::\n\n        >>> @require_partition\n        ... def foo(G, partition):\n        ...     print('partition is valid!')\n        ...\n        >>> G = nx.complete_graph(5)\n        >>> partition = [{0, 1}, {2, 3}, {4}]\n        >>> foo(G, partition)\n        partition is valid!\n        >>> partition = [{0}, {2, 3}, {4}]\n        >>> foo(G, partition)  # doctest: +IGNORE_EXCEPTION_DETAIL\n        Traceback (most recent call last):\n          ...\n        NetworkXError: `partition` is not a valid partition of the nodes of G\n        >>> partition = [{0, 1}, {1, 2, 3}, {4}]\n        >>> foo(G, partition)  # doctest: +IGNORE_EXCEPTION_DETAIL\n        Traceback (most recent call last):\n          ...\n        NetworkXError: `partition` is not a valid partition of the nodes of G\n\n    \"\"\"\n\n    @wraps(func)\n    def new_func(*args, **kw):\n        # Here we assume that the first two arguments are (G, partition).\n        if not is_partition(*args[:2]):\n            raise nx.NetworkXError('`partition` is not a valid partition of'\n                                   ' the nodes of G')\n        return func(*args, **kw)\n    return new_func\n\n\ndef intra_community_edges(G, partition):\n    \"\"\"Returns the number of intra-community edges according to the given\n    partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    The \"intra-community edges\" are those edges joining a pair of nodes\n    in the same block of the partition.\n\n    \"\"\"\n    return sum(G.subgraph(block).size() for block in partition)\n\n\ndef inter_community_edges(G, partition):\n    \"\"\"Returns the number of inter-community edges according to the given\n    partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    The *inter-community edges* are those edges joining a pair of nodes\n    in different blocks of the partition.\n\n    Implementation note: this function creates an intermediate graph\n    that may require the same amount of memory as required to store\n    `G`.\n\n    \"\"\"\n    # Alternate implementation that does not require constructing a new\n    # graph object (but does require constructing an affiliation\n    # dictionary):\n    #\n    #     aff = dict(chain.from_iterable(((v, block) for v in block)\n    #                                    for block in partition))\n    #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])\n    #\n    if G.is_directed():\n        return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()\n    else:\n        return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()\n\n\ndef inter_community_non_edges(G, partition):\n    \"\"\"Returns the number of inter-community non-edges according to the\n    given partition of the nodes of `G`.\n\n    `G` must be a NetworkX graph.\n\n    `partition` must be a partition of the nodes of `G`.\n\n    A *non-edge* is a pair of nodes (undirected if `G` is undirected)\n    that are not adjacent in `G`. The *inter-community non-edges* are\n    those non-edges on a pair of nodes in different blocks of the\n    partition.\n\n    Implementation note: this function creates two intermediate graphs,\n    which may require up to twice the amount of memory as required to\n    store `G`.\n\n    \"\"\"\n    # Alternate implementation that does not require constructing two\n    # new graph objects (but does require constructing an affiliation\n    # dictionary):\n    #\n    #     aff = dict(chain.from_iterable(((v, block) for v in block)\n    #                                    for block in partition))\n    #     return sum(1 for u, v in nx.non_edges(G) if aff[u] != aff[v])\n    #\n    return inter_community_edges(nx.complement(G), partition)\n\n\n@not_implemented_for('multigraph')\n@require_partition\ndef performance(G, partition):\n    \"\"\"Returns the performance of a partition.\n\n    The *performance* of a partition is the ratio of the number of\n    intra-community edges plus inter-community non-edges with the total\n    number of potential edges.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        A simple graph (directed or undirected).\n\n    partition : sequence\n\n        Partition of the nodes of `G`, represented as a sequence of\n        sets of nodes. Each block of the partition represents a\n        community.\n\n    Returns\n    -------\n    float\n        The performance of the partition, as defined above.\n\n    Raises\n    ------\n    NetworkXError\n        If `partition` is not a valid partition of the nodes of `G`.\n\n    References\n    ----------\n    .. [1] Santo Fortunato.\n           \"Community Detection in Graphs\".\n           *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174\n           <https://arxiv.org/abs/0906.0612>\n\n    \"\"\"\n    # Compute the number of intra-community edges and inter-community\n    # edges.\n    intra_edges = intra_community_edges(G, partition)\n    inter_edges = inter_community_non_edges(G, partition)\n    # Compute the number of edges in the complete graph (directed or\n    # undirected, as it depends on `G`) on `n` nodes.\n    #\n    # (If `G` is an undirected graph, we divide by two since we have\n    # double-counted each potential edge. We use integer division since\n    # `total_pairs` is guaranteed to be even.)\n    n = len(G)\n    total_pairs = n * (n - 1)\n    if not G.is_directed():\n        total_pairs //= 2\n    return (intra_edges + inter_edges) / total_pairs\n\n\n@require_partition\ndef coverage(G, partition):\n    \"\"\"Returns the coverage of a partition.\n\n    The *coverage* of a partition is the ratio of the number of\n    intra-community edges to the total number of edges in the graph.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    partition : sequence\n        Partition of the nodes of `G`, represented as a sequence of\n        sets of nodes. Each block of the partition represents a\n        community.\n\n    Returns\n    -------\n    float\n        The coverage of the partition, as defined above.\n\n    Raises\n    ------\n    NetworkXError\n        If `partition` is not a valid partition of the nodes of `G`.\n\n    Notes\n    -----\n    If `G` is a multigraph, the multiplicity of edges is counted.\n\n    References\n    ----------\n    .. [1] Santo Fortunato.\n           \"Community Detection in Graphs\".\n           *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174\n           <https://arxiv.org/abs/0906.0612>\n\n    \"\"\"\n    intra_edges = intra_community_edges(G, partition)\n    total_edges = G.number_of_edges()\n    return intra_edges / total_edges\n\n\ndef modularity(G, communities, weight='weight'):\n    r\"\"\"Returns the modularity of the given partition of the graph.\n\n    Modularity is defined in [1]_ as\n\n    .. math::\n\n        Q = \\frac{1}{2m} \\sum_{ij} \\left( A_{ij} - \\frac{k_ik_j}{2m}\\right)\n            \\delta(c_i,c_j)\n\n    where $m$ is the number of edges, $A$ is the adjacency matrix of\n    `G`, $k_i$ is the degree of $i$ and $\\delta(c_i, c_j)$\n    is 1 if $i$ and $j$ are in the same community and 0 otherwise.\n\n    Parameters\n    ----------\n    G : NetworkX Graph\n\n    communities : list\n        List of sets of nodes of `G` representing a partition of the\n        nodes.\n\n    Returns\n    -------\n    Q : float\n        The modularity of the paritition.\n\n    Raises\n    ------\n    NotAPartition\n        If `communities` is not a partition of the nodes of `G`.\n\n    Examples\n    --------\n    >>> G = nx.barbell_graph(3, 0)\n    >>> nx.algorithms.community.modularity(G, [{0, 1, 2}, {3, 4, 5}])\n    0.35714285714285704\n\n    References\n    ----------\n    .. [1] M. E. J. Newman *Networks: An Introduction*, page 224.\n       Oxford University Press, 2011.\n\n    \"\"\"\n    if not is_partition(G, communities):\n        raise NotAPartition(G, communities)\n\n    multigraph = G.is_multigraph()\n    directed = G.is_directed()\n    m = G.size(weight=weight)\n    if directed:\n        out_degree = dict(G.out_degree(weight=weight))\n        in_degree = dict(G.in_degree(weight=weight))\n        norm = 1 / m\n    else:\n        out_degree = dict(G.degree(weight=weight))\n        in_degree = out_degree\n        norm = 1 / (2 * m)\n\n    def val(u, v):\n        try:\n            if multigraph:\n                w = sum(d.get(weight, 1) for k, d in G[u][v].items())\n            else:\n                w = G[u][v].get(weight, 1)\n        except KeyError:\n            w = 0\n        # Double count self-loops if the graph is undirected.\n        if u == v and not directed:\n            w *= 2\n        return w - in_degree[u] * out_degree[v] * norm\n\n    Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))\n    return Q * norm\n", "path": "networkx/algorithms/community/quality.py"}]}