Statistical limits of correlation detection in trees

DOI10.1214/23-AAP2048MaRDI QIDQ6616873zbMATH OpenFDO

Authors Luca Ganassali, Laurent Massoulié, Guilhem Semerjian

Publication date 9 October 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/23-AAP2048

zbMATH Keywords

combinatoricshypothesis testingrandom graphsstatistical inference

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Parametric hypothesis testing (62F03) Combinatorics in computer science (68R05)

Recommendations

• Correlation detection in trees for planted graph alignment
• Correlated randomly growing graphs
• Exact matching of random graphs with constant correlation
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Correlation of Graph‐Theoretical Indices

Cites work

• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Detection threshold for correlated Erdős-Rényi graphs via densest subgraph
• Edit distance between unlabeled ordered trees
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 7829306 (Why is no real title available?)
• Partial Recovery in the Graph Alignment Problem
• Random graph matching at Otter's threshold via counting chandeliers
• Testing correlation of unlabeled random graphs
• The number of trees
• Weighted Derangements and the Linearization Coefficients of Orthogonal Sheffer Polynomials

Cited in

(10)

• Correlation detection in trees for planted graph alignment
• A computational transition for detecting correlated stochastic block models by low-degree polynomials
• Low-degree hardness of detection for correlated Erdős-Rényi graphs
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Efficiently matching random inhomogeneous graphs via degree profiles
• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
• The algorithmic phase transition of random graph alignment problem
• Faster algorithms for the alignment of sparse correlated Erdős-Rényi random graphs
• Optimal recovery of correlated Erdős-Rényi graphs
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

This page was built for publication: Statistical limits of correlation detection in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6616873)