Session Y12: Inference in Complex Networks

Physics of Inference

Jaynes’s maximum entropy method provides a family of principled models that allow the prediction of a system’s properties as constrained by empirical data (observables). However, their use is often hindered by the degeneracy problem characterized by spontaneous symmetry breaking, where predictions fail. Here we show that degeneracy appears when the corresponding density of states function is not log-concave, which is typically the consequence of nonlinear relationships between the constraining observables. We illustrate this phenomenon on several examples, including from complex networks, combinatorics and classical spin systems (e.g., Blume-Emery-Griffiths lattice-spin models). Exploiting these nonlinear relationships we then propose a solution to the degeneracy problem for a large class of systems via transformations that render the density of states function log-concave. The effectiveness of the method is demonstrated on real-world network data. Finally, we discuss the implications of these findings on the relationship between the geometrical properties of the density of states function and phase transitions in spin systems.   

Nonparametric inference of network structure and dynamics

The network structure of complex systems determine their function and serve as evidence for the evolutionary mechanisms that lie behind them. Despite considerable effort in recent years, it remains an open challenge to formulate general descriptions of the large-scale structure of network systems, and how to reliably extract such information from data. Although many approaches have been proposed, few methods attempt to gauge the statistical significance of the uncovered structures, and hence the majority cannot reliably separate actual structure from stochastic fluctuations. Due to the sheer size and high-dimensionality of many networks, this represents a major limitation that prevents meaningful interpretations of the results obtained with such nonstatistical methods. In this talk, I will show how these issues can be tackled in a principled and efficient fashion by formulating appropriate generative models of network structure that can have their parameters inferred from data. By employing a Bayesian description of such models, the inference can be performed in a nonparametric fashion, that does not require any \emph{a priori} knowledge or \emph{ad hoc} assumptions about the data. I will show how this approach can be used to perform model comparison, and how hierarchical models yield the most appropriate trade-off between model complexity and quality of fit based on the statistical evidence present in the data. I will also show how this general approach can be elegantly extended to networks with edge attributes, that are embedded in latent spaces, and that change in time. The latter is obtained via a fully dynamic generative network model, based on arbitrary-order Markov chains, that can also be inferred in a nonparametric fashion. Throughout the talk I will illustrate the application of the methods with many empirical networks such as the internet at the autonomous systems level, the global airport network, the network of actors and films, social networks, citations among websites, voting correlations among politicians, co-occurrence of disease-causing genes and others.   

Identification of dynamical models of chemical reaction networks

Current first-principles models of complex chemistry, such as combustion reaction networks, often give inaccurate predictions of the time variation of chemical species. Moreover, the high complexity and dimensionality of these models render them impractical for real-time prediction and control of chemical network processes. These limitations have motivated us to search for an alternative paradigm that is able to both identify the correct model from the observed dynamical data and reduce complexity while preserving the underlying network structure. In this talk, I will present one such modeling paradigm under the scenarios of complete and incomplete observability of the dynamics. The proposed approach is applicable to combustion chemistry and a range of other chemical reaction networks.   

Infering Networks From Collective Dynamics

How can we infer direct physical interactions between pairs of units from only knowing the units' time series? Here we present a dynamical systems' view on collective network dynamics, and propose the concept of a \emph{dynamics' space} to reveal interaction networks from time series. We present two examples: one, where the time series stem from standard ordinary differential equations, and a second, more abstract, where the time series exhibits only partial information about the units' states. We apply the latter to neural circuit dynamics where the observables are spike timing data, i.e. only a discrete, state-dependent outputs of the neurons. These results may help revealing network structure for systems where direct access to dynamics is simpler than to connectivity, cf.~[1,2,3]. \\[5mm] This is work with Jose Casadiego, Srinivas Gorur Shandilya, Mor Nitzan, Hauke Haehne and Dimitra Maoutsa. \\[5mm] [1] M. Timme, Phys. Rev. Lett. 98:224101 (2007). http://dx.doi.org/10.1103/PhysRevLett.98.224101 \\[2mm] [2] S.G. Shandilya & M. Timme, New J. Phys. 13, 013004 (2011). http://dx.doi.org/10.1088/1367-2630/13/1/013004 \\[2mm] [3] M. Timme & J. Casadiego, Phys. Rev. A 47:343001 (2014) - Invited Review. http://dx.doi.org/10.1088/1751-8113/47/34/343001   

Clustering means geometry in networks

Using maximum-likelihood estimation techniques, any real network data can be fit to essentially any network model, inferring the most likely values of the model parameters for the network. However there is one caveat. The results of such fitting are not spurious but meaningful and predictive, only if the network is a typical network in the unbiased ensemble of random graphs with the inferred values of model parameters. Therefore, given a particular combination of a real network and a model, the first question one has to answer is what structural properties of the network ensure that this network is a typical element in the ensemble of random graphs defined by the model. This question is usually highly intractable, explaining why it is almost never answered before the fitting/inference task is performed. Inspired by recent observations that random geometric graphs reproduce many structural and dynamical properties of a variety of real networks, we find the network structural properties that guarantee that networks that have these properties are in fact geometric, meaning that latent space network models are their true models. Specifically we prove that peculiar organization of clustering observed in real networks is one of the main such properties. In other words, maximum-entropy random graphs with specific clustering properties, which are quite different from the clustering properties of random graphs in the Strauss model, are actually soft random geometric graphs with a specific form of the connection probability function. Using this function we can then infer the coordinates of nodes in a latent space for any given network, and reliably check if the network is a typical network in the resulting ensemble of soft random geometric graphs. If it is, then the inferred coordinates are meaningful and real, and can be used for prediction tasks with proved guarantees that the results of such predictions are reliable and not just transient artifacts.