Matching recovery threshold for correlated random graphs

DOI10.1214/23-AOS2305MaRDI QIDQ6183756zbMATH OpenFDO

Authors

Publication date 4 January 2024

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.14650, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-4/Matching-recovery-threshold-for-correlated-random-graphs/10.1214/23-AOS2305.full

zbMATH Keywords

correlated Erdős-Rényi random graphinformation thresholdmatching recovery

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: For two correlated graphs which are independently sub-sampled from a common ErdH{o}s-R'enyi graph $mathbfG(n,p)$, we wish to recover their emph{latent} vertex matching from the observation of these two graphs emph{without labels}. When $p=n^{-alpha+o(1)}$ for $alphain(0,1]$, we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

Recommendations

• Exact matching of random graphs with constant correlation
• Partial Recovery in the Graph Alignment Problem
• Efficient random graph matching via degree profiles
• Aligning random graphs with a sub-tree similarity message-passing algorithm

Cites work

• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Correlated randomly growing graphs
• Efficient random graph matching via degree profiles
• Exact matching of random graphs with constant correlation
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Introduction to Random Graphs
• Load balancing and orientability thresholds for random hypergraphs
• Performance of global load balancing by local adjustment
• Seeded graph matching for correlated Erdős-Rényi graphs
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Testing correlation of unlabeled random graphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The cycle structure of random permutations
• The densest subgraph problem in sparse random graphs
• The planted matching problem: sharp threshold and infinite-order phase transition
• The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation

Cited in

(8)

• Exact matching of random graphs with constant correlation
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Correlation detection in trees for planted graph alignment
• Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
• The planted matching problem: sharp threshold and infinite-order phase transition
• Partial Recovery in the Graph Alignment Problem
• Information Recovery in Shuffled Graphs via Graph Matching
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

This page was built for publication: Matching recovery threshold for correlated random graphs

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