Large scale structure in complex networks

复杂网络中的大规模结构

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

Many systems of scientific and technological importance can be represented as networks: the Internet, the power grid, airline and road networks, biological networks, and social networks, to name just a few. The last fifteen years have seen a wave of advances in mathematical and computational techniques for understanding these systems and analyzing the massive troves of network data that are becoming available. The work to be undertaken under this funding will do two things: (1) develop fundamental new mathematics to enhance our understanding of the structure and function of networks of all types, and (2) employ that mathematical foundation in the creation of new measures, metrics, and computer algorithms for practical application to real-world network problems. The work will draw on mathematical methods from two areas in which the PI has worked extensively: Statistics (Bayesian inference) and spectral theory. Using these tools the PI and his students and collaborators will develop techniques to tackle a range of network problems, including: the detection of communities of interacting nodes or individuals within larger networks; the identification of the most influential or core nodes with a network; the understanding and prediction of spreading processes on networks, including the spread of diseases over human contact networks; fast and scalable computer algorithms for the analysis of network data on the largest scales; and specific applications to a range of technological, social, and information networks.This grant will fund a three-year research effort to develop fundamental mathematical tools for understanding large, real-world networks such as the Internet, the World Wide Web, biological networks, epidemiological contact networks, social networks, and others. The proposed work focuses on large-scale network properties, rather than local properties, and will employ techniques mainly from two fields, spectral methods and statistical inference. Recent work by the PI's group and others has produced significant advances, including a number of results revealing deep and previously unsuspected connections between spectral and inference methods. These advances have opened up substantial avenues for new research whose exploration is the primary goal of the proposed work. Specific projects to be undertaken include the development of random matrix and free probability methods for computing spectra of complex networks within several widely used structural models; development of new inference algorithms for features such as core/periphery structure and centrality, particularly based on belief propagation methods; connections between inference and spectral methods, particularly via the Hashimoto operator which appears in the theory of graph zeta functions; spectral localization and the development of improved spectral centrality measures; applications to network processes such as percolation and disease transmission, which can be treated using belief propagation and hence connected to spectral properties of graphs; applications to spectral algorithms for multiway community detection and other large-scale structure detection problems; connections between spectral and inference methods derived from relaxations of the likelihood function; and model selection methods for network inference.

许多具有科学和技术重要性的系统都可以用网络来表示：互联网、电网、航空和公路网络、生物网络和社交网络等等。 在过去的15年里，数学和计算技术取得了一波又一波的进步，这些进步有助于理解这些系统，并分析大量可用的网络数据。 在这笔资金下进行的工作将做两件事：（1）开发基础新数学，以提高我们对所有类型网络的结构和功能的理解，以及（2）将数学基础用于创建新的测量，度量和计算机算法，以实际应用于现实世界的网络问题。 这项工作将借鉴PI广泛工作的两个领域的数学方法：统计学（贝叶斯推断）和谱理论。 利用这些工具，PI及其学生和合作者将开发技术来解决一系列网络问题，包括：检测大型网络中相互作用的节点或个人的社区;识别网络中最具影响力或核心节点;理解和预测网络上的传播过程，包括疾病在人类接触网络上的传播;快速和可扩展的计算机算法，用于分析最大规模的网络数据;以及一系列技术、社会和信息网络的具体应用。该基金将资助一项为期三年的研究工作，以开发用于理解大型现实世界网络（如互联网、万维网、生物网络、流行病接触网络、社交网络等。 拟议的工作重点是大规模的网络属性，而不是本地属性，并将采用技术主要来自两个领域，频谱方法和统计推断。 PI的团队和其他人最近的工作取得了重大进展，包括一些结果揭示了光谱和推理方法之间的深刻和以前未被怀疑的联系。这些进展为新的研究开辟了实质性的途径，其探索是拟议工作的主要目标。 拟开展的具体项目包括：开发随机矩阵和自由概率方法，用于在几种广泛使用的结构模型内计算复杂网络的频谱;开发新的推理算法，用于核心/外围结构和中心性等特征，特别是基于置信传播方法;推理和谱方法之间的联系，特别是通过桥本算子出现在理论的图形zeta函数;谱局部化和改进谱中心性测度的发展;应用于网络过程，如渗流和疾病传播，可以使用置信传播进行处理，因此与图的谱特性有关;应用于多路社区检测和其他大规模结构检测问题的谱算法;从似然函数的松弛推导出的频谱和推理方法之间的联系;以及网络推理的模型选择方法。