# Source code for graph_tool.inference.modularity

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# graph_tool -- a general graph manipulation python module
#
# Copyright (C) 2006-2018 Tiago de Paula Peixoto <tiago@skewed.de>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

from .. import _prop, perfect_prop_hash

from .. dl_import import dl_import
dl_import("from . import libgraph_tool_inference as libinference")

[docs]def modularity(g, b, weight=None):
r"""
Calculate Newman's modularity of a network partition.

Parameters
----------
g : :class:~graph_tool.Graph
Graph to be used.
b : :class:~graph_tool.PropertyMap
Vertex property map with the community partition.
weight : :class:~graph_tool.PropertyMap (optional, default: None)
Edge property map with the optional edge weights.

Returns
-------
Q : float
Newman's modularity.

Notes
-----

Given a specific graph partition specified by prop, Newman's modularity
[newman-modularity-2006]_ is defined as:

.. math::

Q = \frac{1}{2E} \sum_r e_{rr}- \frac{e_r^2}{2E}

where :math:e_{rs} is the number of edges which fall between
vertices in communities s and r, or twice that number if :math:r = s, and
:math:e_r = \sum_s e_{rs}.

If weights are provided, the matrix :math:e_{rs} corresponds to the sum
of edge weights instead of number of edges, and the value of :math:E
becomes the total sum of edge weights.

Examples
--------
>>> g = gt.collection.data["football"]
>>> gt.modularity(g, g.vp.value_tsevans)
0.5744393497...

References
----------
.. [newman-modularity-2006] M. E. J. Newman, "Modularity and community
structure in networks", Proc. Natl. Acad. Sci. USA 103, 8577-8582 (2006),
:doi:10.1073/pnas.0601602103, :arxiv:physics/0602124
"""

if b.value_type() not in ["bool", "int16_t", "int32_t", "int64_t",
"unsigned long"]:
b = perfect_prop_hash([b])
Q = libinference.modularity(g._Graph__graph,
_prop("e", g, weight),
_prop("v", g, b))
return Q