RUI: Network Evolution with Unobserved Mechanisms

Middlebury College, Middlebury VT

Investigators

Abstract

Many social networks evolve through mechanisms that are only partially recorded in data. For example, the observed formation of a link between two new friends in a social network might depend on an unobserved third person who introduced them. In this project, the investigators will develop new mathematical models of social networks which evolve through unobserved events and use these models to analyze real-world data. The research team will focus on two broad phenomena to model. First, they will study how networks of multiway interactions become separated by agent attributes over time. Second, the team will study how social hierarchies shape and are shaped by networks of cooperative endeavor. This work will take place in collaboration with practicing anthropologists and theoretical biologists. The results of both workstreams will highlight the strengths and limitations of simple theories of human social behavior and will also generate novel analysis algorithms for several types of network data. Undergraduate students will be recruited via a summer work-study program to pursue these workstreams. These students will collaborate on interdisciplinary teams, learning best practices for collaborative research alongside technical skills. For each of the systems under study the team will pursue three primary technical tasks. The first task will be to perform data analysis and use this analysis to formulate a stochastic latent-variable model of the system. The second task will be to analyze the long-run behavior of each modeled system, with an eye towards detecting phase transitions: qualitative shifts in macroscopic behavior as system parameters are smoothly varied. The team will determine parameter regimes in which models of growing hypergraphs exhibit self-reinforcing separation or in which models of cooperation exhibit stable social hierarchies. These phase transitions will be determined using compartmental equations and associated analysis. The third task will be to develop efficient algorithms for inference: learning model parameters from observed data. The team will approach the inference problem through the classical lens of maximum-likelihood estimation. To perform optimization efficiently in the latent-variable setting, the team will develop and implement expectation-maximization algorithms for these models. The team will also develop online stochastic variants specialized for the case of very large data. In the case of hypergraph separation models, the inference framework will lead to novel algorithms for model-based hypergraph clustering, while in the case of cooperative hierarchies inference will lead to novel dynamic embedding algorithms for time-stamped undirected graphs. The team will validate the proposed models through parameter recovery experiments on synthetic data. The team will then use these models to analyze real-world network data sets across several social domains. 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.