Root and community inference on the latent growth process of a network

• 成果类型: Article
• 署名作者: Crane, Harry; Xu, Min
• 署名单位: Rutgers University System; Rutgers University New Brunswick
• 刊物名称: JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY
• ISSN/ISSBN: 1369-7412
• DOI: 10.1093/jrsssb/qkad102
• 发表日期: 2023
• 关键词: preferential attachment; trees; MODEL

摘要

Many statistical models for networks overlook the fact that most real-world networks are formed through a growth process. To address this, we introduce the Preferential Attachment Plus Erd & odblac;s-R & eacute;nyi model, where we let a random network G be the union of a preferential attachment (PA) tree T and additional Erd & odblac;s-R & eacute;nyi (ER) random edges. The PA tree captures the underlying growth process of a network where vertices/edges are added sequentially, while the ER component can be regarded as noise. Given only one snapshot of the final network G, we study the problem of constructing confidence sets for the root node of the unobserved growth process; the root node can be patient zero in an infection network or the source of fake news in a social network. We propose inference algorithms based on Gibbs sampling that scales to networks with millions of nodes and provide theoretical analysis showing that the size of the confidence set is small if the noise level of the ER edges is not too large. We also propose variations of the model in which multiple growth processes occur simultaneously, reflecting the growth of multiple communities; we use these models to provide a new approach to community detection.