Source code for graph_tool.inference.latent_multigraph

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# graph_tool -- a general graph manipulation python module
# Copyright (C) 2006-2020 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 _prop

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

from numpy import sqrt

[docs]def latent_multigraph(g, epsilon=1e-8, max_niter=0, verbose=False): r"""Infer latent Poisson multigraph model given an "erased" simple graph. Parameters ---------- g : :class:`~graph_tool.Graph` Graph to be used. This is expected to be a simple graph. epsilon : ``float`` (optional, default: ``1e-8``) Convergence criterion. max_niter : ``int`` (optional, default: ``0``) Maximum number of iterations allowed (if ``0``, no maximum is assumed). verbose : ``boolean`` (optional, default: ``False``) If ``True``, display verbose information. Returns ------- u : :class:`~graph_tool.Graph` Latent graph. w : :class:`~graph_tool.EdgePropertyMap` Edge property map with inferred edge multiplicities. Notes ----- This implements the expectation maximization algorithm described in [peixoto-latent-2020]_ which consists in iterating the following steps until convergence: 1. In the "expectation" step we obtain the marginal mean multiedge multiplicities via: .. math:: w_{ij} = \begin{cases} \frac{\theta_i\theta_j}{1-\mathrm{e}^{-\theta_i\theta_j}} & \text{ if } G_{ij} = 1,\\ \theta_i^2 & \text{ if } i = j,\\ 0 & \text{ otherwise.} \end{cases} 2. In the "maximization" step we use the current values of :math:`\boldsymbol w` to update the values of :math:`\boldsymbol \theta`: .. math:: \theta_i = \frac{d_i}{\sqrt{\sum_jd_j}}, \quad\text{ with } d_i = \sum_jw_{ji}. The equations above are adapted accordingly if the supplied graph is directed, where we have :math:`\theta_i\theta_j\to\theta_i^-\theta_j^+`, :math:`\theta_i^2\to\theta_i^-\theta_i^+`, and :math:`\theta_i^{\pm}=\frac{d_i^{\pm}}{\sqrt{\sum_jd_j^{\pm}}}`, with :math:`d^+_i = \sum_jw_{ji}` and :math:`d^-_i = \sum_jw_{ij}`. A single EM iteration takes time :math:`O(V + E)`. If enabled during compilation, this algorithm runs in parallel. Examples -------- >>> g =["as-22july06"] >>> gt.scalar_assortativity(g, "out") (-0.198384..., 0.001338...) >>> u, w = gt.latent_multigraph(g) >>> gt.scalar_assortativity(u, "out", eweight=w) (-0.048426..., 0.034526...) References ---------- .. [peixoto-latent-2020] Tiago P. Peixoto, "Latent Poisson models for networks with heterogeneous density", :arxiv:`2002.07803` """ g = g.copy() theta_out = g.degree_property_map("out").copy("double") theta_out.fa /= sqrt(theta_out.fa.sum()) if g.is_directed(): theta_in = g.degree_property_map("in").copy("double") theta_in.fa /= sqrt(theta_in.fa.sum()) else: theta_in = theta_out w = g.new_ep("double", 1) libinference.latent_multigraph(g._Graph__graph, _prop("e", g, w), _prop("v", g, theta_out), _prop("v", g, theta_in), epsilon, max_niter, verbose) return g, w