Structure and Function in Large-Scale Complex Networks

许多与科学、技术和医学相关的系统可以被表示为网络，包括互联网、电网、大脑中的神经网络，以及疾病传播的个体之间的接触网络。该项目侧重于使用数学和计算机模型对这种网络系统进行建模，并将解决两个领域的需求。第一个问题涉及我们如何首先确定网络的结构。例如，为了建立疾病爆发的模型，人们必须确定人与人之间的接触模式，以便了解传播。然而，已知网络结构的实验测量是不准确的，并且可能给出误导性的结果。为了规避不可能完成的完美测量任务，该项目将结合最先进的计算和数学技术，制定方法，即使在基础数据不可靠的情况下，也能准确估计网络结构。其结果将是新的方法，使更可靠的计算网络数量和精确的误差范围的指示，可用于告知科学判断。该项目的第二个重点是开发新的计算机算法，用于使用称为信念传播的数学技术计算网络数量。这些算法将专注于网络对故障或攻击的恢复能力、流行病学过程的结果或网络的大规模结构特征等计算。例如，信念传播方法允许在给定接触网络结构和疾病本身的基本参数的情况下计算将被疾病感染的预期人数。该项目旨在开发新的数学方法，用于分析网络数据，用于在网络上发生的过程的自洽解决方案，以及在存在测量误差的情况下对网络特性的最佳估计。两个研究主题中的第一个主题将集中在消息传递方法上，这是一类强大的自洽方法，用于求解网络系统的结构和动态特性。这些方法虽然有用，但长期以来一直受到技术限制的制约，这些限制限制了它们在无环路或几乎无环路的网络中的使用。在成功的初步研究的基础上，该项目将展示如何克服这些限制并开发新一代的消息传递方法，这些方法适用于现实网络，包括那些具有高密度环路的网络。一系列的具体应用将被追求和开发的方法也将作为新的正式发展的基础，如新的随机图模型，网络结构相变理论，以及非常大的网络的光谱计算。第二个主题将侧重于从丰富但可能不可靠的数据源中对网络结构进行估计的严格方法。大多数对网络结构的经验观察都包含这样或那样的测量误差，但这些误差很少被考虑，部分原因是缺乏一个全面的数学框架来处理它们。该项目将基于测量过程的正式模型，结合统计和机器学习工具，包括贝叶斯方法、期望最大化算法和蒙特卡罗技术，开发这样一个框架。结果将是一套新的工具，使从业者能够从嘈杂的数据中对网络及其属性做出可靠的估计，并量化这些估计中的不确定性水平。与计算机科学、生物学和社会科学领域的专家合作，这些方法的具体应用将被开发用于诸如互联网、生态网络和社会网络等系统。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.