Network Reconstruction and Community Detection from Dynamics

We present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are also inherently used to improve the accuracy of the reconstruction which, in turn, can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.

Figure 1

Comparison between joint and separate reconstruction with community detection for a PP model with $N=1000$, $⟨k⟩=15$, and $B=10$. (a) Normalized mutual information (NMI) between inferred and planted node partitions, as a function of the model parameter $\epsilon$, for several values of the number of samples $M$ from the Ising model described in the text. (b) Posterior similarity between planted and inferred networks, for the same cases as in (a). The vertical line marks the detectability threshold $\epsilon =1/\sqrt{⟨k⟩}$.

Figure 2

Reconstruction results for simulated dynamics on empirical networks, comparing separate and joint reconstruction with community detection. (a) and (b) correspond to a SIS dynamics on global airport data, using ${\tau }_{ij}=\tau$, $\gamma =1$, for different values of the infection probability $\tau$ and node activity $a$ (defined as the number of infection events per node), and (c) and (d) the Ising model on a food web, using $J_{ij}=1$ and $h_i=0$. The dashed red line corresponds to the inverse correlation method for the Ising model. The solid vertical line marks the critical value for each model.

Figure 3

Reconstruction of a food web network [46] from $M={10}^4$ samples of an Ising model at critical temperature. Edges marked in red are erroneous in the reconstruction. (a) Original network. (b) Optimal correlation thresholding. (c) Inverse correlations. (d) Joint reconstruction with community detection. The legends show the values of the posterior similarity [Eq. (11)].

Figure 4

Reconstruction of the interactions between members of the lower house of the Brazilian congress from the voting patterns of the 2007–2011 session, according to the Ising model. The node colors indicate the inferred groups. The edge thickness shows the posterior probability for each edge, and the color shows the magnitude of the coupling $J_{ij}$. The labels show the most frequent party membership for each group.

Figure 5

Reconstruction of the directed network of influence between $N=1833$ twitter users from 58224 retweets, using a SI infection model. The hierarchical division represents the inferred fit of the nested DC-SBM (see Refs. [51, 52] for details on the layout algorithm), and the edge colors indicate the infection probabilities ${\tau }_{ij}$ as shown in the legend. The text labels show the dominating country membership for the users in each group.