Dynamic network models: Entrance boundary and continuum scaling limits, condensation phenomena and probabilistic combinatorial optimization

动态网络模型：入口边界和连续尺度限制、凝聚现象和概率组合优化

• 批准号: 1606839
• 负责人: Sreekalyani Bhamidi
• 金额: $ 10万
• 依托单位: University of North Carolina at Chapel Hill
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1606839&HistoricalAwards=false
• 关键词: Dynamic; network; models; Entrance; boundary

The recent explosion in the amount of empirical network data, ranging from brain networks of interacting neurons, to the Internet, transportation, social networks, and other self-organized behavior, has stimulated vigorous activity in a multitude of fields, including biology, statistical physics, statistics, mathematics, and computer science to model and understand these systems. The aim of this research project is to develop systematic mathematical theory to understand dynamic networks: systems that evolve over time through probabilistic rules. The investigator plans to develop robust mathematical techniques to understand how macroscopic connectivity arises via microscopic interactions between agents in a network. One important direct application is whether a message or a disease is able to reach -- or at risk of reaching -- a significant fraction of the population of interest. Mathematical techniques used to understand such questions have unexpected connections to combinatorial optimization, where one is interested in designing optimal networks between individuals, particularly by considering an important concept known as the minimal spanning tree. The project will also explore swarm optimization algorithms (inspired by the collective behavior of simple individuals such as ants) and their ability to solve hard optimization problems via probabilistic interaction rules through stigmergy (where the network of interacting agents changes the underlying environment which then effects the interaction of the agents). An important component of the project is involvement of students at all levels, including the development of undergraduate research seminars and research projects. Understanding the metric structure of the giant component and the critical scaling window in inhomogeneous random graph models has been daunting, yet for several decades the community of combinatorial probabilists has seen it as key to understanding more complicated strong disorder systems. The project aims to develop a unified set of tools through dynamic encoding of network models to understand the metric scaling of the internal structure of maximal components in the critical regime. The investigator plans to show convergence to continuum limiting objects based on tilted inhomogeneous continuum random trees and in particular to prove universality for many of the major families of random graph models. Scaling exponents of key susceptibility functions in the barely subcritical regime will be studied. The relation between metric structure of components in the critical regime and the entrance boundary of Markov processes such as the multiplicative coalescent will be explored. The entire program is the first step in understanding the minimal spanning tree on the giant component under strong disorder. These models have spawned a wide array of universality conjectures from statistical physics. The project will also study optimization algorithms and meta-heuristics inspired by reinforcing interacting particle systems and stigmergy, providing qualitative insights and quantitative predictions on hard models in probabilistic combinatorial optimization.

近年来，经验网络数据的数量激增，从相互作用的神经元组成的大脑网络到互联网、交通、社交网络和其他自组织行为，这刺激了包括生物学、统计物理学、统计学、数学和计算机科学在内的众多领域对这些系统进行建模和理解的积极活动。该研究项目的目的是开发系统的数学理论来理解动态网络：通过概率规则随时间演变的系统。研究人员计划开发强大的数学技术，以了解宏观连通性如何通过网络中代理之间的微观相互作用产生。一个重要的直接应用是，一种信息或一种疾病是否能够接触到-或有可能接触到-很大一部分感兴趣的人口。用于理解这些问题的数学技术与组合优化有着意想不到的联系，在组合优化中，人们对设计个体之间的最优网络感兴趣，特别是通过考虑一个被称为最小生成树的重要概念。该项目还将探索群优化算法（灵感来自蚂蚁等简单个体的集体行为）及其通过污名化（其中交互代理的网络改变底层环境，然后影响底层环境）通过概率交互规则解决硬优化问题的能力。代理的交互）。该项目的一个重要组成部分是各级学生的参与，包括本科生研究研讨会和研究项目的发展。理解非齐次随机图模型中巨组分的度量结构和临界尺度窗口一直令人生畏，然而几十年来，组合概率学家社区将其视为理解更复杂的强无序系统的关键。该项目旨在通过网络模型的动态编码开发一套统一的工具，以了解临界状态下最大组件内部结构的度量标度。研究人员计划显示收敛到连续限制对象的基础上倾斜的非均匀连续随机树，特别是要证明许多主要家庭的随机图模型的普遍性。将研究在勉强次临界状态下关键磁化率函数的标度指数。我们将探讨临界状态下分量的度规结构与马尔可夫过程（如乘法结合）的入口边界之间的关系。整个程序是理解强无序下巨分支上最小生成树的第一步。这些模型从统计物理学中衍生出了一系列广泛的普适性假设。该项目还将研究优化算法和元算法，这些算法和元算法的灵感来自于增强相互作用的粒子系统和stigmergy，为概率组合优化中的硬模型提供定性见解和定量预测。