From 64e2b5f8c020f524664d7e698402172a53245620 Mon Sep 17 00:00:00 2001 From: Moritz Emanuel Beber Date: Sat, 8 Sep 2012 19:24:56 +0200 Subject: Adds modularity measure for communities. --- networkx/algorithms/community/__init__.py | 1 + networkx/algorithms/community/modularity.py | 93 ++++++++++++++++++++++ .../algorithms/community/tests/test_modularity.py | 27 +++++++ 3 files changed, 121 insertions(+) create mode 100644 networkx/algorithms/community/modularity.py create mode 100644 networkx/algorithms/community/tests/test_modularity.py (limited to 'networkx/algorithms') diff --git a/networkx/algorithms/community/__init__.py b/networkx/algorithms/community/__init__.py index 1d0fbbdf..3b09edf0 100644 --- a/networkx/algorithms/community/__init__.py +++ b/networkx/algorithms/community/__init__.py @@ -3,4 +3,5 @@ from networkx.algorithms.community.centrality import * from networkx.algorithms.community.community_generators import * from networkx.algorithms.community.kclique import * from networkx.algorithms.community.kernighan_lin import * +from networkx.algorithms.community.modularity import * from networkx.algorithms.community.quality import * diff --git a/networkx/algorithms/community/modularity.py b/networkx/algorithms/community/modularity.py new file mode 100644 index 00000000..dbc09809 --- /dev/null +++ b/networkx/algorithms/community/modularity.py @@ -0,0 +1,93 @@ +# modularity.py - functions for computing modularity of a partition +# +# Copyright 2011 Ben Edwards . +# Copyright 2011 Aric Hagberg . +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Functions for computing the modularity of a partition.""" +from __future__ import division + +from itertools import product + +import networkx as nx +from .community_utils import is_partition + + +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``, + `k_i` is the degree of `i` and `\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 + ------ + NetworkXError + 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 nx.NetworkXError('communities is not a partition of G') + + 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_modularity.py b/networkx/algorithms/community/tests/test_modularity.py new file mode 100644 index 00000000..c2a34754 --- /dev/null +++ b/networkx/algorithms/community/tests/test_modularity.py @@ -0,0 +1,27 @@ +# test_modularity.py - unit tests for the community.modularity module +# +# Copyright 2011 Ben Edwards . +# Copyright 2011 Aric Hagberg . +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Unit tests for the :mod:`networkx.algorithms.community.modularity` +module. + +""" +from __future__ import division + +from nose.tools import assert_almost_equal + +import networkx as nx + + +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)) -- cgit v1.2.1 From cbdf7b125c5dc1b1ef367c8cd72877d3f6910cc5 Mon Sep 17 00:00:00 2001 From: Jeffrey Finkelstein Date: Mon, 25 Jul 2016 23:07:57 -0400 Subject: Moves modularity into quality module. --- networkx/algorithms/community/__init__.py | 1 - networkx/algorithms/community/modularity.py | 93 ---------------------- networkx/algorithms/community/quality.py | 93 +++++++++++++++++++++- .../algorithms/community/tests/test_modularity.py | 27 ------- .../algorithms/community/tests/test_quality.py | 16 +++- 5 files changed, 104 insertions(+), 126 deletions(-) delete mode 100644 networkx/algorithms/community/modularity.py delete mode 100644 networkx/algorithms/community/tests/test_modularity.py (limited to 'networkx/algorithms') diff --git a/networkx/algorithms/community/__init__.py b/networkx/algorithms/community/__init__.py index 3b09edf0..1d0fbbdf 100644 --- a/networkx/algorithms/community/__init__.py +++ b/networkx/algorithms/community/__init__.py @@ -3,5 +3,4 @@ from networkx.algorithms.community.centrality import * from networkx.algorithms.community.community_generators import * from networkx.algorithms.community.kclique import * from networkx.algorithms.community.kernighan_lin import * -from networkx.algorithms.community.modularity import * from networkx.algorithms.community.quality import * diff --git a/networkx/algorithms/community/modularity.py b/networkx/algorithms/community/modularity.py deleted file mode 100644 index dbc09809..00000000 --- a/networkx/algorithms/community/modularity.py +++ /dev/null @@ -1,93 +0,0 @@ -# modularity.py - functions for computing modularity of a partition -# -# Copyright 2011 Ben Edwards . -# Copyright 2011 Aric Hagberg . -# Copyright 2015 NetworkX developers. -# -# This file is part of NetworkX. -# -# NetworkX is distributed under a BSD license; see LICENSE.txt for more -# information. -"""Functions for computing the modularity of a partition.""" -from __future__ import division - -from itertools import product - -import networkx as nx -from .community_utils import is_partition - - -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``, - `k_i` is the degree of `i` and `\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 - ------ - NetworkXError - 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 nx.NetworkXError('communities is not a partition of G') - - 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/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_modularity.py b/networkx/algorithms/community/tests/test_modularity.py deleted file mode 100644 index c2a34754..00000000 --- a/networkx/algorithms/community/tests/test_modularity.py +++ /dev/null @@ -1,27 +0,0 @@ -# test_modularity.py - unit tests for the community.modularity module -# -# Copyright 2011 Ben Edwards . -# Copyright 2011 Aric Hagberg . -# Copyright 2015 NetworkX developers. -# -# This file is part of NetworkX. -# -# NetworkX is distributed under a BSD license; see LICENSE.txt for more -# information. -"""Unit tests for the :mod:`networkx.algorithms.community.modularity` -module. - -""" -from __future__ import division - -from nose.tools import assert_almost_equal - -import networkx as nx - - -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)) 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)) -- cgit v1.2.1