Testing network correlation efficiently via counting trees
This addresses the problem of efficiently detecting network correlations for researchers in network analysis, representing a strong specific gain rather than a broad breakthrough.
The paper tackles the problem of testing whether two networks are edge-correlated via a latent vertex correspondence by proposing a test statistic based on counting co-occurrences of signed trees. The result is a test that runs in n^{2+o(1)} time and succeeds with high probability under conditions including a correlation coefficient ρ^2 > α ≈ 0.338, significantly improving prior work in statistical accuracy, running time, and graph sparsity.
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 co-occurrences of signed trees for a family of non-isomorphic trees. When the two networks are Erdős-Rényi random graphs $\mathcal{G}(n,q)$ that are either independent or correlated with correlation coefficient $ρ$, our test runs in $n^{2+o(1)}$ time and succeeds with high probability as $n\to\infty$, provided that $n\min\{q,1-q\} \ge n^{-o(1)}$ and $ρ^2>α\approx 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.