TESTING NETWORK CORRELATION EFFICIENTLY VIA COUNTING TREES
成果类型：
Article
署名作者：
Mao, Cheng; Wu, Yihong; Xu, Jiaming; Yu, Sophie h
署名单位：
University System of Georgia; Georgia Institute of Technology; Yale University; Duke University; University of Pennsylvania
刊物名称：
ANNALS OF STATISTICS
ISSN/ISSBN：
0090-5364
DOI：
10.1214/23-AOS2261
发表日期：
2024
页码：
2483-2505
关键词：
摘要：
We propose a new procedure for testing whether two networks are edgecorrelated through some latent vertex correspondence. The test statistic is based on counting the cooccurrences of signed trees for a family of nonisomorphic trees. When the two networks are Erdos-R & eacute;nyi random graphs G(n, q) that are either independent or correlated with correlation coefficient rho, our test runs in n(2+o(1)) time and succeeds with high probability as n -> infinity, provided that n min{q, 1 - q} >= n(-o(1)) and rho(2) > alpha approximate to 0.338, where alpha is Otter's constant so that the number of unlabeled trees with K edges grows as (1/alpha)(K). This significantly improves the prior work in terms of statistical accuracy, running time and graph sparsity.