Detection threshold for correlated Erdős-Rényi graphs via densest subgraph

DOI10.1109/TIT.2023.3265009MaRDI QIDQ6574816zbMATH OpenFDO

Authors Jian Ding, Hang Du

Publication date 18 July 2024

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TIT.2023.3265009

zbMATH Keywords

detecting edge correlationErdős-Rényi random graphshypothesis testing problemunlabeled nodes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypothesis testing in multivariate analysis (62H15)

Cited in

(10)

• Statistical limits of correlation detection in trees
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• 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
• 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
• On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
• 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: Detection threshold for correlated Erdős-Rényi graphs via densest subgraph

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