Structure and Function in Large-Scale Complex Networks

大规模复杂网络的结构和功能

• 批准号: 2005899
• 负责人: Mark Newman
• 金额: $ 32.92万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2024-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2005899&HistoricalAwards=false
• 关键词: Structure; Function; Large; Scale; Complex

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.

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

项目成果

Message passing methods on complex networks

复杂网络上的消息传递方法

• DOI: 10.1098/rspa.2022.0774
• 发表时间: 2023
• 期刊: Physical and Engineering Sciences
• 作者: Newman, M. E.

Ranking with multiple types of pairwise comparisons

通过多种类型的成对比较进行排名

• DOI: 10.1098/rspa.2022.0517
• 发表时间: 2022
• 期刊: Physical and Engineering Sciences
• 作者: Newman, Mark E.

Cutting Through the Noise to Infer Autonomous System Topology

消除噪音来推断自治系统拓扑

• DOI: 10.1109/infocom48880.2022.9796874
• 发表时间: 2022
• 期刊: Proceedings of IEEE INFOCOM 2022
• 作者: Leyba, Kirtus G.;Daymude, Joshua J.;Young, Jean-Gabriel;Newman, M. E.;Rexford, Jennifer;Forrest, Stephanie
• 通讯作者: Forrest, Stephanie

Bayesian inference of network structure from unreliable data

• DOI: 10.1093/comnet/cnaa046
• 发表时间: 2020-12
• 期刊: J. Complex Networks
• 作者: Jean-Gabriel Young;George T. Cantwell;Mark E. J. Newman

Representative community divisions of networks

• DOI: 10.1038/s42005-022-00816-3
• 发表时间: 2022-02-17
• 期刊: COMMUNICATIONS PHYSICS
• 影响因子: 5.5
• 作者: Kirkley, Alec;Newman, M. E. J.
• 通讯作者: Newman, M. E. J.