Phys. Rev. Lett. 115, 188701 (2015) - Sampling Motif-Constrained Ensembles of Networks

Loading web-font TeX/Script/Regular

Go Mobile »
Access by Staats- und Universitaetsbibliothek Bremen

Sampling Motif-Constrained Ensembles of Networks

Rico Fischer, Jorge C. Leitão, Tiago P. Peixoto, and Eduardo G. Altmann

Phys. Rev. Lett. 115, 188701 – Published 29 October 2015

Abstract

The statistical significance of network properties is conditioned on null models which satisfy specified properties but that are otherwise random. Exponential random graph models are a principled theoretical framework to generate such constrained ensembles, but which often fail in practice, either due to model inconsistency or due to the impossibility to sample networks from them. These problems affect the important case of networks with prescribed clustering coefficient or number of small connected subgraphs (motifs). In this Letter we use the Wang-Landau method to obtain a multicanonical sampling that overcomes both these problems. We sample, in polynomial time, networks with arbitrary degree sequences from ensembles with imposed motifs counts. Applying this method to social networks, we investigate the relation between transitivity and homophily, and we quantify the correlation between different types of motifs, finding that single motifs can explain up to 60% of the variation of motif profiles.

Received 30 July 2015

DOI:

© 2015 American Physical Society

Authors & Affiliations

Rico Fischer¹, Jorge C. Leitão¹, Tiago P. Peixoto², and Eduardo G. Altmann¹

¹Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany
²Institut für Theoretische Physik, Universität Bremen, Hochschulring 18, 28359 Bremen, Germany

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand

Issue

Vol. 115, Iss. 18 — 30 October 2015

Reuse & Permissions

General Relativity

2015 - General Relativity’s Centennial

The editors of the Physical Review journals have curated a collection of landmark papers on General Relativity to celebrate its centennial. These papers are currently free to read.

International Year Of Light

The Physical Review Journals Celebrate the International Year of Light

The editors of the Physical Review journals revisit papers that represent important breakthroughs in the field of optics. The articles covered are free to read throughout 2015.

Images

Figure 1
Multicanonical sampling of exponential random graphs with imposed clustering avoids the limitations of canonical sampling. The ensemble $G$ corresponds to $k$ -regular undirected networks with $N = 640$ and degree $k = 4$ . The observable is the clustering coefficient $s = c$ (proportional to the number of triangles, $n_{△}$ ). The main plot shows $⟨ c ⟩$ (and standard deviation) as a function of the inverse temperature $β$ obtained by canonical (symbols) and multicanonical (continuous thick line) sampling. Inset: the distribution $ρ_{β} (c)$ for $β = 3.54 \approx β_{PT}$ obtained by the two methods. Canonical samplings used $5 \times 10^{5}$ MCMC steps for equilibration, before another $5 \times 10^{5}$ steps were used for estimation. After these steps, the value of $β$ was slowly increased ( $β ↑$ ) or decreased ( $β ↓$ ) and the process repeated. The multicanonical sampling used 20 Wang-Landau steps to estimate $ρ_{0} (c)$ (each step used 5 tunneling steps) [20, 32].
Reuse & Permissions
Figure 2
Efficiency of the multicanonical method to sample networks with constraints. The computational cost (in number of MCMC steps) to generate an independent realization of a network in the $k$ -regular ensemble with $k = 3$ is plotted as a function of $N$ . In the canonical method close to the critical $β$ , this requires passing the minimum of $ρ_{β} (c)$ (inset of Fig. 1). We measured that the height of this barrier increases as $Δ ρ \approx 0.4 N$ , which leads to an exponential increase in the cost (dashed line). Sampling independent realizations in the multicanonical method requires, at most, a tunneling (the number of MCMC steps to do $c = 0 \mapsto c = 1 \mapsto c = 0$ ) [32]. The measured tunneling time (circles and full line) scales polynomially. Inset: convergence of the relative error in the logarithm of the density of states (entropy) during convergence of the Wang-Landau algorithm, estimated comparing the measured value with the exact value on $c = 1$ . The saturation of the error observed for a large number of steps does not hinder the sampling of any $c$ (see Ref. [33] for methods to overcome the saturation).
Reuse & Permissions
Figure 3
Relationship between clustering $c$ and assortativity $r$ in the Email network of Ref. [38]. The assortativity $r^{*}$ is higher than in a random network with the same degree sequence, but lower than in a typical network with a fixed clustering $c^{*}$ . The plot shows $r$ and $c$ of different networks: the Email network (green), a typical fully random network (red), a typical random network with $c = c^{*}$ (black), and networks sampled using the multicanonical method from an ensemble with equal probability for networks with the same $c$ (blue dots). Inset: $⟨ c ⟩$ obtained using the canonical method.
Reuse & Permissions
Figure 4
Motifs are correlated to each other in blocks. (a) The Pearson correlation coefficient [ $R_{i j} = (⟨ n_{i} n_{j} ⟩ - ⟨ n_{i} ⟩ ⟨ n_{j} ⟩) / σ_{n_{i}} σ_{n_{j}}$ ] between motifs $i$ and $j$ , computed by varying the constrained motif (in a range which includes the values of the real and random networks [40]). (b) Upper panel: Motif profile [17] built from the $z$ score $z_{j}$ vs $j$ [ $z_{j} = (n_{j} - ⟨ n_{j} ⟩) / σ_{n_{j}}$ , where $n_{j}$ is the number of motifs $j$ and $⟨ \dots ⟩$ and $σ_{j}$ are the average and standard deviation in the $β = 0$ ensemble]. Different lines correspond to the $z_{j}$ of the real network ( $z_{j}^{*}$ , blue line) and the expected $z_{j} s$ in the constrained ensemble in which $n_{i}$ is equal to the $n_{i}^{*}$ of the real network, where $i$ is the constrained motif shown in the legend ( $z_{j} = z_{j}^{*}$ for $j = i$ ). Middle panel: the correlation between the profiles shown in the upper panel, i.e., between the profile $z$ of the real network and the profile $z^{'}$ of the motif- $i$ constrained network (as a function of $i$ ), computed as $R_{z z^{'}} = (⟨ z z^{'} ⟩ - ⟨ z ⟩ ⟨ z^{'} ⟩) / σ_{z}^{2}$ , where $⟨ \dots ⟩$ and $σ_{z}$ were computed over $j \neq i$ . Lower panel: comparison of the $z$ score shown in the upper panel (blue line) and the alternative $z$ score obtained computing $⟨ \dots ⟩$ and $σ_{j}$ in the ensemble constrained by $n_{i} = n_{i}^{*}$ , where $i$ is indicated in the legend ( $z_{j} \equiv 0$ for $j = i$ ).
Reuse & Permissions

1 of 4