Abstract:
|
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 ER 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 diverges, provided that the network is not overly too sparse or dense and rho^2>alpha~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.
|