Inferring the Past on Markovian Models of Networks

统计和数据科学的一个主要挑战是网络数据的分析。网络数据描述了个体实体之间的相互作用和关系。最突出的例子是社交网络数据，但其他重要的例子包括互联网超链接网络、蛋白质相互作用网络、城市之间的航线网络和人与人之间的疾病传播网络。这些互动网络通常从几个个体开始，随着时间的推移，它们会吸引、感染或招募更多的成员，并创造更多的互动。该项目的目标是开发能够准确描述现实世界网络增长过程的概率模型，并使用这些模型从大规模网络数据中提取重要信息。算法和软件包将被开发出来，使用户能够回答诸如哪些人是社交网络的最早成员，或者该网络包含一个或多个正在增长的社区等问题。该项目的研究成果将应用于公共卫生、社会科学、计算机科学和国家安全等领域。该项目还为研究生提供研究培训机会。PI开发的框架将随机网络建模为优先连接树（PA）和Erdos-Renyi （ER）随机边的组合。PA树描述了网络的成长过程，可以看作是信号，而ER随机边可以看作是噪声。该框架包括许多现有的网络模型作为特殊情况，并允许从业者权衡模型复杂性和计算复杂性。将开发基于Gibbs抽样的可扩展方法来解决推理问题，例如为根节点构建置信集或推断网络节点的社区成员。基于现有的优先依恋模型的概率特性，还将进行理论分析，以评估作为信噪比函数的统计推断的质量，并了解这些问题的信息限制。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A major challenge in statistics and data science is the analysis of network data. Network data describe interactions and relationships between individual entities. The most prominent example is social network data, but other important examples include internet hyperlink networks, protein interaction networks, air route networks between cities, and disease transmission networks between people. These interaction networks generally start with a few individuals and, as time goes on, they attract, infect, or recruit more members and create more interactions. The goal of this project is to develop probabilistic models that accurately describe the growth process of real-world networks and to use these models to extract important information from large scale network data. Algorithms and software packages will be developed that enable users to answer questions such as, which individuals were the earliest members of a social network, or does the network contain one growing community or multiple? The results of this project will have applications in public health, social science, computer science, and national security. The project also provides research training opportunities for graduate students. The framework developed by the PI models a random network as a combination of a preferential attachment (PA) tree and Erdos-Renyi (ER) random edges. The PA tree describes the growth process of a network and may be regarded as the signal and the ER random edges can be interpreted as the noise. This framework includes many existing network models as special cases and allows practitioners to trade-off model complexity and computational complexity. Scalable methodology based on Gibbs sampling will be developed to tackle inference problems such as constructing confidence sets for the root nodes or inferring the community membership of the nodes of a network. Theoretical analysis, based on existing probabilistic properties of preferential attachment models, will also be conducted to assess the quality of statistical inference as a function of the signal-to-noise ratio and to understand the information limits of these problems.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.