Many systems of interest in science, technology, and medicine can be represented as networks, including the Internet, the power grid, neural networks in the brain, and the contact networks between individuals over which diseases spread. This project focuses on modeling of such networked systems using mathematical and computer models and will address two areas of need. The first concerns how we determine the structure of networks in the first place. To make a model of, for instance, a disease outbreak, one must determine the pattern of contacts between people in order to understand spread. Experimental measurements of network structure, however, are known to have inaccuracies and can give misleading results. To circumvent the impossible task of making perfect measurements, this project will use a combination of state-of-the-art computational and mathematical techniques to formulate methods for making accurate estimates of network structure even when the underlying data are unreliable. The result will be new ways to make more trustworthy calculations of network quantities and precise indications of the margin of error that can be used to inform scientific judgment. The second focus of this project is the development of new computer algorithms for calculation of network quantities using the mathematical technique known as belief propagation. These algorithms will focus on calculations such as resilience of networks to failure or attack, outcomes of epidemiological processes, or large-scale structural features of networks. As an example, belief propagation methods permit calculation of the expected number of individuals who will be infected by a disease given the structure of a contact network and fundamental parameters of the disease itself.
This project aims to develop new mathematical methods for the analysis of network data, for the self-consistent solution of processes taking place on networks, and for optimal estimation of network properties in the presence of measurement error. The first of two research themes will focus on message passing methods, a powerful class of self-consistent methods for solving for the structural and dynamical properties of networked systems. Though useful, these methods have long been handicapped by technical limitations that restrict their use to loop-free, or nearly loop-free, networks. Building on successful preliminary studies, this project will show how these limitations can be overcome and develop a new generation of message passing methods that work on realistic networks, including those with a high density of loops. A range of specific applications will be pursued and the methods developed will also serve as the foundation for new formal developments, such as new random graph models, theories of structural phase transitions in networks, and the computation of spectra for very large networks. A second theme will focus on rigorous methods for making estimates of network structure from rich but potentially unreliable data sources. Most empirical observations of network structure contain measurement error of one kind or another, but these errors are rarely considered, in part for lack of a comprehensive mathematical framework for treating them. This project will develop such a framework, based on formal models of the measurement process coupled with statistical and machine learning tools including Bayesian methods, expectation-maximization algorithms, and Monte Carlo techniques. The result will be a new set of tools that allow practitioners to make reliable estimates of networks and their properties from noisy data and to quantify the level of uncertainty in those estimates. In collaboration with domain experts in computer science, biology, and the social sciences, specific applications of these methods will be developed for systems such as the Internet, ecological networks, and social networks.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
