Scalable Statistical Inference in Small-World Networks

社交网络经常表现出“小世界特征”。例如，朋友之间通常会有很多共同的朋友，但无论社交网络的大小，大多数人的熟人数量都是有限的。这种网络的另一个充分证明的特征是“六度分离属性”，即大多数人彼此之间有少量的社会联系。尽管它们无处不在，复杂网络的常见统计模型通常不会生成具有这些属性的图。因此，本项目的主要目标是解决小世界网络普遍缺乏可信和可处理的统计模型的问题。具体来说，pi将为这些网络的推理开发一个新的框架，包括统计模型，快速和可扩展的算法，以及支持理论。这些模型和方法将通过开发和部署对大型图表进行采样的技术来进行经验验证，以帮助评估它们。这种新的理解将有助于新闻、卫生保健和法律领域正在进行的跨学科合作。现有的小世界网络的概率结构，即表现出低直径、稀疏性和传递性的随机图，往往是特别的，因此往往不适合统计推断。在这个项目中，pi将制定和分析小世界网络的可解释统计模型；并基于光谱技术和局部采样为这些模型开发可扩展的统计推断。为此，pi将开发和探索一系列具有高维潜在特征的网络模型。pi将分析传统算法在这种情况下的表现，并将开发和分析本地抽样算法，例如受访者驱动的抽样。本文还将研究社区检测的信息论极限。这笔拨款将支持针对威斯康星大学麦迪逊分校新本科数据科学学位的中级本科生的两门课程的开发。这些课程旨在扩大数据科学和社会网络分析的参与。这项资助也将支持培养统计和数学方面的博士研究生。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.