This is the authors' abstract. We don't add key points for this paper.
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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Mao et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: