Dr. Shankar Bhamidi received NSF grant on "Dynamic network models on entrance boundary and continuum scaling limits, condensation phenomena and probabilistic combinatorial optimization"
February 15, 2017The last few years have witnessed an explosion in the amount of empirical data on real networks motivating an array of mathematical models for the evolution of such networks. Examples range from biological networks (brain networks of interacting neurons), information transmission (Internet), transportation, social networks and swarm intelligence and the evolution of self-organized behavior through the interactions of simple agents. This has stimulated vigorous activity in a multitude of fields, including biology, statistical physics, statistics, mathematics and computer science to understand these models and quantify their predictions and relevance to real systems. The aim of this grant is to develop systematic mathematical theory to understand Dynamic networks: systems that evolve over time through probabilistic rules. Using models motivated by colloidal chemistry, we will developing robust mathematical techniques to understand how macroscopic connectivity in the network arises via microscopic interactions between agents in the network. This is of importance in areas such as epidemic modeling and social networks wherein core questions of interest include if a disease or a message is able to reach 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. The techniques developed in the grant in particular will be used to understand asymptotics in the large network limit for one of the most fundamental of such objects, the Minimal spanning tree. Lastly we will explore meta-heuristics including 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 particles). An important component of the grant is involvement of students at all levels including the development of undergraduate research seminars and research projects.
The nature of emergence of the giant component and the critical scaling window in random graph models has stimulated enormous amount of work in probabilistic combinatorics since the middle of the last century; most techniques deal with gross features such as maximal component sizes. Understanding the metric structure of these components in inhomogeneous random graphs has been particularly daunting, despite being being the key to understanding more complicated strong disorder systems. The proposal develops a unified set of tools through dynamic encoding of network models of interest and tracking the entire trajectory of evolution of these systems in order to understand the metric scaling of the internal structure of maximal components in the critical regime. We aim to show convergence to continuum limiting objects based on tilted inhomogeneous continuum random trees and in particular prove universality for many of the major families of random graph models. Connections between these questions and structural properties of dynamic constructions of random graph models, in particular 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 scaling limits of fundamental models in strong disorder including the minimal spanning tree on the giant component. These models have spawned a wide array of universality conjectures from statistical physics. In a related direction, we will study optimization algorithms and meta-heuristics inspired by reinforcing interacting particle systems and stigmergy and their relationship to key probabilistic systems such as reinforced random walks and stochastic dynamical systems. The aim in this direction is to provide qualitative insights and quantitative predictions on hard models in probabilistic combinatorial optimization such as the traveling salesman problem.