Testing correlation of unlabeled random graphs
DOI10.1214/22-aap1786arXiv2008.10097MaRDI QIDQ6109918
Yihong Wu, Jiaming Xu, Sophie H. Yu
Publication date: 31 July 2023
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.10097
hypothesis testinggraph matchingcycle decompositionErdős-Rényi graphsunlabeled graphsconditional second moment method
Hypothesis testing in multivariate analysis (62H15) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstruction and estimation in the planted partition model
- Community detection in sparse random networks
- Dense subgraphs in random graphs
- The all-or-nothing phenomenon in sparse linear regression
- Correlated randomly growing graphs
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- The graph matching problem
- Community detection in dense random networks
- The number of trees
- Efficient random graph matching via degree profiles
- Introduction to Random Graphs
- Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
- Spectral alignment of correlated Gaussian matrices
- Settling the Sharp Reconstruction Thresholds of Random Graph Matching
- Seeded graph matching via large neighborhood statistics
- Introduction to nonparametric estimation
- Testing correlation of unlabeled random graphs
This page was built for publication: Testing correlation of unlabeled random graphs