Dynamic Networks: Probabilistic Models and Inference Problems

Princeton University, Princeton NJ

Investigators

Abstract

Networks play a fundamental role in many areas of science, such as the network of friendships in sociology and protein-protein interaction networks in biology. At the heart of problems in these areas is a need to understand underlying structures in the relevant network, such as geometric structure and community structure. Many networks evolve and grow over time and this leaves a mark on their underlying structure. The broad goal of this project is to understand how the growth of a network interacts with other underlying structures such as community structure. The project focuses on a mathematical understanding of fundamental network models that are common to many applications. Developing such a mathematical theory can lead to fundamental insights that can be applied across multiple disciplines, as well as to connections between disciplines that can lead to further cross-disciplinary explorations. This project studies a wide range of problems involving probabilistic models of dynamic networks. The project aims to build novel probabilistic theory to analyze and provide insight into such models, as well as to build and analyze novel models that shed light on new phenomena. A main focus is on models of growing networks, which are abundant in the social sciences, economics, and biology. In particular, the project will investigate the influence of the seed graph in growing random graph models. In doing so, the award will develop novel probabilistic tools to obtain quantitative results on the limits of branching processes, which are of independent interest more widely in probability theory and related fields. A second theme of the project will be the study of community detection in growing networks by introducing probabilistic models of growing networks with community structure. This perspective lends itself to relevant new questions, such as detecting communities from networks observed at multiple time points. Finally, the award will also study stochastic processes on networks, resulting in enhanced understanding of how information spreads on networks. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.