Social networks often exhibit "small-world features". For instance, friends typically share many common friends, but most individuals have a limited number of close acquaintances irrespective of the size of the network. Another well-documented feature of such networks is the "six degrees of separation property", whereby most people are a small number of social connections away from one another. Despite their ubiquity, common statistical models of complex networks do not typically generate graphs with these properties. Therefore, the main goal of this project is to address the general lack of plausible and tractable statistical models of small-world networks. Specifically, the PIs will develop a novel framework for the inference of these networks, including statistical models, fast and scalable algorithms, as well as supporting theory. These models and methods will be empirically validated through the development and deployment of techniques that sample large graphs in ways that helps assess them. This new understanding will contribute to ongoing interdisciplinary collaborations in journalism, health care, and law.
Existing probabilistic constructions of small-world networks, i.e., random graphs exhibiting low diameter, sparsity and transitivity, tend to be ad-hoc and, hence, often not suitable for statistical inference. In this project, the PIs will formulate and analyze interpretable statistical models of small-world networks; and develop scalable statistical inference for such models based on both spectral techniques and local sampling. For this purpose, the PIs will develop and explore a family of network models with high-dimensional latent features. The PIs will analyze how traditional algorithms perform in this regime, and will develop and analyze local sampling algorithms, such as respondent-driven sampling. The information-theoretic limit of community detection will also be studied. This grant will support the development of two courses aimed at intermediate undergraduates in UW- Madison's new undergraduate data science degree. These courses will aim to broaden engagement in both data science and social network analysis. This grant will also support the training of PhD students in both Statistics and Mathematics.
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.
