Testing network correlation efficiently via counting trees
提出一种新方法，通过计数有符号树的共现来检验两个网络是否存在边相关性，适用于稀疏随机图，在统计精度和运行时间上优于现有方法。
We propose a new procedure for testing whether two networks are edge-correlated 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 Erdős–Rényi random graphs G(n,q) that are either independent or correlated with correlation coefficient ρ, our test runs in n2+o(1) time and succeeds with high probability as n→∞, provided that nmin{q,1−q}≥n−o(1) and ρ2>α≈0.338, where α is Otter’s constant so that the number of unlabeled trees with K edges grows as (1/α)K. This significantly improves the prior work in terms of statistical accuracy, running time and graph sparsity.