Large scale structure in complex networks

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

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.