# latent_multigraph#

graph_tool.inference.latent_multigraph(g, epsilon=1e-08, max_niter=0, verbose=False)[source]#

Infer latent Poisson multigraph model given an “erased” simple graph.

Parameters:
gGraph

Graph to be used. This is expected to be a simple graph.

epsilonfloat (optional, default: 1e-8)

Convergence criterion.

max_niterint (optional, default: 0)

Maximum number of iterations allowed (if 0, no maximum is assumed).

verboseboolean (optional, default: False)

If True, display verbose information.

Returns:
uGraph

Latent graph.

wEdgePropertyMap

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:

$\begin{split}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}\end{split}$
2. In the “maximization” step we use the current values of $$\boldsymbol w$$ to update the values of $$\boldsymbol \theta$$:

$\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 $$\theta_i\theta_j\to\theta_i^-\theta_j^+$$, $$\theta_i^2\to\theta_i^-\theta_i^+$$, and $$\theta_i^{\pm}=\frac{d_i^{\pm}}{\sqrt{\sum_jd_j^{\pm}}}$$, with $$d^+_i = \sum_jw_{ji}$$ and $$d^-_i = \sum_jw_{ij}$$.

A single EM iteration takes time $$O(V + E)$$.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

References

Tiago P. Peixoto, “Latent Poisson models for networks with heterogeneous density”, Phys. Rev. E 102 012309 (2020) DOI: 10.1103/PhysRevE.102.012309 [sci-hub, @tor], arXiv: 2002.07803

Examples

>>> g = gt.collection.data["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...)