Merge pull request #1729 from jfinkels/modularity

Adds modularity measure for communities.

2 files changed, 104 insertions, 5 deletions

diff --git a/networkx/algorithms/community/quality.py b/networkx/algorithms/community/quality.py
index 2c4b6c45..955d01ef 100644
--- a/networkx/algorithms/community/quality.py
+++ b/networkx/algorithms/community/quality.py
@@ -1,6 +1,6 @@
 # quality.py - functions for measuring partitions of a graph
 #
-# Copyright 2015 NetworkX developers.
+# Copyright 2015-2016 NetworkX developers.
 #
 # This file is part of NetworkX.
 #
@@ -13,11 +13,24 @@ communities).
 from __future__ import division
 
 from functools import wraps
+from itertools import product
 
 import networkx as nx
+from networkx import NetworkXError
 from networkx.utils import not_implemented_for
 
-__all__ = ['coverage', 'performance']
+__all__ = ['coverage', 'modularity', 'performance']
+
+
+class NotAPartition(NetworkXError):
+    """Raised if a given collection is not a partition.
+
+    """
+
+    def __init__(self, G, collection):
+        msg = '{} is not a valid partition of the graph {}'
+        msg = msg.format(G, collection)
+        super(NotAPartition, self).__init__(msg)
 
 
 def is_partition(G, partition):
@@ -249,3 +262,79 @@ def coverage(G, partition):
     intra_edges = intra_community_edges(G, partition)
     total_edges = G.number_of_edges()
     return intra_edges / total_edges
+
+
+def modularity(G, communities, weight='weight'):
+    r"""Returns the modularity of the given partition of the graph.
+
+    Modularity is defined in [1]_ as
+
+    .. math::
+
+        Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right)
+            \delta(c_i,c_j)
+
+    where *m* is the number of edges, *A* is the adjacency matrix of
+    `G`, :math:`k_i` is the degree of *i* and :math:`\delta(c_i, c_j)`
+    is 1 if *i* and *j* are in the same community and 0 otherwise.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+
+    communities : list
+        List of sets of nodes of `G` representing a partition of the
+        nodes.
+
+    Returns
+    -------
+    Q : float
+        The modularity of the paritition.
+
+    Raises
+    ------
+    NotAPartition
+        If `communities` is not a partition of the nodes of `G`.
+
+    Examples
+    --------
+    >>> G = nx.barbell_graph(3, 0)
+    >>> nx.modularity(G, [{0, 1, 2}, {3, 4, 5}])
+    0.35714285714285704
+
+    References
+    ----------
+    .. [1] M. E. J. Newman *Networks: An Introduction*, page 224.
+       Oxford University Press, 2011.
+
+    """
+    if not is_partition(G, communities):
+        raise NotAPartition(G, communities)
+
+    multigraph = G.is_multigraph()
+    directed = G.is_directed()
+    m = G.size(weight=weight)
+    if directed:
+        out_degree = dict(G.out_degree(weight=weight))
+        in_degree = dict(G.in_degree(weight=weight))
+        norm = 1 / m
+    else:
+        out_degree = dict(G.degree(weight=weight))
+        in_degree = out_degree
+        norm = 1 / (2 * m)
+
+    def val(u, v):
+        try:
+            if multigraph:
+                w = sum(d.get(weight, 1) for k, d in G[u][v].items())
+            else:
+                w = G[u][v].get(weight, 1)
+        except KeyError:
+            w = 0
+        # Double count self-loops if the graph is undirected.
+        if u == v and not directed:
+            w *= 2
+        return w - in_degree[u] * out_degree[v] * norm
+
+    Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))
+    return Q * norm
diff --git a/networkx/algorithms/community/tests/test_quality.py b/networkx/algorithms/community/tests/test_quality.py
index b8ee94a3..920e2dec 100644
--- a/networkx/algorithms/community/tests/test_quality.py
+++ b/networkx/algorithms/community/tests/test_quality.py
@@ -14,9 +14,11 @@ from __future__ import division
 
 from nose.tools import assert_almost_equal
 
-from networkx.generators.classic import barbell_graph
-from networkx.algorithms.community.quality import coverage
-from networkx.algorithms.community.quality import performance
+import networkx as nx
+from networkx import barbell_graph
+from networkx import coverage
+from networkx import performance
+
 
 class TestPerformance(object):
     """Unit tests for the :func:`performance` function."""
@@ -50,3 +52,11 @@ class TestCoverage(object):
         G = barbell_graph(3, 0)
         partition = [{0, 1, 2}, {3, 4, 5}]
         assert_almost_equal(6 / 7, coverage(G, partition))
+
+
+def test_modularity():
+    G = nx.barbell_graph(3, 0)
+    C = [{0, 1, 4}, {2, 3, 5}]
+    assert_almost_equal(-16 / (14 ** 2), nx.modularity(G, C))
+    C = [{0, 1, 2}, {3, 4, 5}]
+    assert_almost_equal((35 * 2) / (14 ** 2), nx.modularity(G, C))