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

University Of North Carolina At Chapel Hill, Chapel Hill NC

Investigators

Abstract

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.