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 inherently also 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. The observed functional behavior of a wide variety large-scale systems is often the result of a network of pairwise interactions. However, in many cases these interactions are hidden from us, either because they are impossible to be measured directly, or because their measurement can be done only at significant experimental cost. [27, 28] . In this work, we approach the problem of network reconstruction in a manner that is different from the aforementioned methods in two important ways. First, we employ a nonparametric Bayesian formulation of the problem, which yields a full posterior distribution of possible networks that are compatible with the observed dynamical behavior. Second, we perform network reconstruction jointly with community detection [29] , where at the same time we infer the edges of the underlying network, we also infer its modular structure [30] . As we will show, while network reconstruction and community detection are desirable goals on their own, joining these two tasks has a synergistic effect, whereby the detection of communities significantly increases the accuracy of the reconstruction, which in turn improves the discovery of the communities, when compared to performing these tasks in isolation. Some other approaches combine community detection with functional observation. Berthet et al. [31] derived necessary conditions for the exact recovery of group assignments for dense weighted networks generated with community structure given observed microstates of an Ising model. Hoffmann et al. [32] proposed a method to infer community structure from time-series data that bypasses network reconstruction, by employing instead a direct modeling of the dynamics given the group assignments. However, neither of these approaches attempt to perform network reconstruction together with community detection. Furthermore, they are tied down to one particular inverse problem, and as we will show, our general approach can be easily extended to an open-ended variety of functional models. Bayesian network reconstruction -We approach the network reconstruction task similarly to the situation where the network edges are measured directly, but via an uncertain process [33, 34] : If D is the measurement of some process that takes place on a network, we can define a posterior distribution for the underlying adjacency matrix A via Bayes' rule, where P (D|A) is an arbitrary forward model for the dynamics given the network, P (A) is the prior information on the network structure, and P (D) = A P (D|A)P (A) is a normalization constant comprising the total evidence for the data D. We can unite reconstruction with community detection via an at first seemingly minor, but ultimately consequential modification of the above equation, where we introduce a structured prior P (A|b) where b represents the partition of the network in communities, i.e. b = {b i }, where b i ∈ {1, . . . , B} is group membership of node i. This partition is unknown, and is inferred together with the network itself, via the joint posterior distribution P (A, b|D) = P (D|A)P (A|b)P (b) P (D) . The prior P (A|b) is an assumed generative model for the network structure. In our work, we will use the degreecorrected stochastic block model (DC-SBM) [35] , which
Peixoto REF recently proposed the most closely related work in an algorithm designed to jointly reconstruct network structure and community labels assuming a stochastic block model structure and highlights the benefits of recovering the full posterior distribution of networks.
Network reconstruction and community detection from dynamics
Phys. Rev. Lett. 123, 128301 (2019)
Medicine Physics Computer Science Mathematics