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-2023 Tiago de Paula Peixoto <>
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU Lesser 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 Lesser General Public License for more
# details.
# You should have received a copy of the GNU Lesser General Public License
# along with this program. If not, see <>.

from .. import Graph, GraphView, _get_rng, _prop, PropertyMap, \
    perfect_prop_hash, Vector_size_t, group_vector_property
from . blockmodel import DictState
from . util import *
import numpy as np

from . base_states import *

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

[docs] def modularity(g, b, gamma=1., weight=None): r""" Calculate Newman's (generalized) modularity of a network partition. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. b : :class:`~graph_tool.VertexPropertyMap` Vertex property map with the community partition. gamma : ``float`` (optional, default: ``1.``) Resolution parameter. weight : :class:`~graph_tool.EdgePropertyMap` (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 =["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])[0] Q = libinference.modularity(g._Graph__graph, gamma, _prop("e", g, weight), _prop("v", g, b)) return Q
[docs] class ModularityState(MCMCState, MultiflipMCMCState, MultilevelMCMCState, GibbsMCMCState, DrawBlockState): r"""Obtain the partition of a network according to the maximization of Newman's modularity. .. danger:: Using modularity maximization is almost always **a terrible idea**. Modularity maximization is a substantially inferior method to the inference-based ones that are implemented in ``graph-tool``, since it does not possess any kind of statistical regularization. Among many other problems, the method tends to massively overfit empirical data. For a more detailed explanation see `“Modularity maximization considered harmful” <>`_, as well as [peixoto-descriptive-2021]_. Do not use this approach in the analysis of networks without understanding the consequences. This algorithm is included only for comparison purposes. In general, the inference-based approaches based on :class:`~graph_tool.inference.BlockState`, :class:`~graph_tool.inference.NestedBlockState`, and :class:`~graph_tool.inference.PPBlockState` should be universally preferred. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be partitioned. b : :class:`~graph_tool.PropertyMap` (optional, default: ``None``) Initial partition. If not supplied, a partition into a single group will be used. eweight : :class:`~graph_tool.EdgePropertyMap` (optional, default: ``None``) Edge multiplicities (for multigraphs). """ def __init__(self, g, b=None, eweight=None): self.g = GraphView(g, directed=False) if b is None: self.b = self.g.new_vp("int32_t") elif isinstance(b, PropertyMap): self.b = self.g.own_property(b).copy("int32_t") else: self.b = self.g.new_vp("int32_t", vals=b) if eweight is None: eweight = g.new_ep("int", 1) elif eweight.value_type() != "int32_t": eweight = g.own_property(eweight.copy(value_type="int32_t")) else: eweight = g.own_property(eweight) self.eweight = eweight = Vector_size_t() self.err = Vector_size_t() = self.g self._abg = self._state = libinference.make_modularity_state(self) self._entropy_args = dict(gamma=1.) def __copy__(self): return self.copy()
[docs] def copy(self, g=None, b=None): r"""Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.""" return ModularityState(g=g if g is not None else self.g, b=b if b is not None else self.b)
def __getstate__(self): return dict(g=self.g, b=self.b) def __setstate__(self, state): self.__init__(**state) def __repr__(self): return "<ModularityState object with %d blocks, for graph %s, at 0x%x>" % \ (self.get_B(), str(self.g), id(self))
[docs] def get_B(self): r"Returns the total number of blocks." rs = np.unique(self.b.fa) return len(rs)
[docs] def get_Be(self): r"""Returns the effective number of blocks, defined as :math:`e^{H}`, with :math:`H=-\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}`, where :math:`n_r` is the number of nodes in group r. """ w = np.bincount(self.b.fa) w = np.array(w, dtype="double") w = w[w>0] w /= w.sum() return np.exp(-(w*log(w)).sum())
[docs] @copy_state_wrap def entropy(self, gamma=1., **kwargs): r"""Return the unnormalized negative generalized modularity. Notes ----- The unnormalized negative generalized modularity is defined as .. math:: -\sum_{ij}\left(A_{ij}-\gamma \frac{k_ik_j}{2E}\right) Where :math:`A_{ij}` is the adjacency matrix, :math:`k_i` is the degree of node :math:`i`, and :math:`E` is the total number of edges. """ eargs = self._get_entropy_args(locals(), ignore=["self", "kwargs"]) if len(kwargs) > 0: raise ValueError("unrecognized keyword arguments: " + str(list(kwargs.keys()))) return self._state.entropy(eargs)
def _get_entropy_args(self, kwargs, ignore=None): kwargs = dict(self._entropy_args, **kwargs) if ignore is not None: for a in ignore: kwargs.pop(a, None) ea = libinference.modularity_entropy_args() ea.gamma = kwargs["gamma"] del kwargs["gamma"] if len(kwargs) > 0: raise ValueError("unrecognized entropy arguments: " + str(list(kwargs.keys()))) return ea
[docs] def modularity(self, gamma=1): r"""Return the generalized modularity. Notes ----- The generalized modularity is defined as .. math:: \frac{1}{2E}\sum_{ij}\left(A_{ij}-\gamma \frac{k_ik_j}{2E}\right) Where :math:`A_{ij}` is the adjacency matrix, :math:`k_i` is the degree of node :math:`i`, and :math:`E` is the total number of edges. """ Q = self.entropy(gamma=gamma) return -Q / (2 * self.g.num_edges())
def _mcmc_sweep_dispatch(self, mcmc_state): return libinference.modularity_mcmc_sweep(mcmc_state, self._state, _get_rng()) def _multiflip_mcmc_sweep_dispatch(self, mcmc_state): return libinference.modularity_multiflip_mcmc_sweep(mcmc_state, self._state, _get_rng()) def _multilevel_mcmc_sweep_dispatch(self, mcmc_state): return libinference.modularity_multilevel_mcmc_sweep(mcmc_state, self._state, _get_rng()) def _gibbs_sweep_dispatch(self, gibbs_state): return libinference.modularity_gibbs_sweep(gibbs_state, self._state, _get_rng())