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 解决硬优化问题的能力（其中交互代理的网络改变了底层环境，然后影响代理之间的相互作用）。该项目的一个重要组成部分是各级学生的参与，包括本科生研究研讨会和研究项目的发展。理解非齐次随机图模型中巨型组件的度量结构和临界缩放窗口一直是令人畏惧的，但几十年来，组合概率学家社区一直将其视为理解更复杂的强无序系统的关键。该项目旨在通过网络模型的动态编码来开发一套统一的工具，以了解关键状态下最大组件的内部结构的度量缩放。研究人员计划展示基于倾斜非齐次连续随机树的连续极限对象的收敛性，特别是证明随​​机图模型的许多主要系列的普遍性。将研究勉强亚临界状态下关键磁化率函数的标度指数。将探讨临界状态中组件的度量结构与马尔可夫过程（例如乘法合并）的入口边界之间的关系。整个程序是理解强无序下巨型构件上的最小生成树的第一步。这些模型从统计物理学中衍生出了一系列广泛的普遍性猜想。该项目还将研究受增强相互作用粒子系统和 stigmergy 启发的优化算法和元启发式算法，为概率组合优化中的硬模型提供定性见解和定量预测。