latent_multigraph

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

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

[peixoto-latent-2020]

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...)