Inferring the Past on Markovian Models of Networks

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

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.