Parallel tempering for the planted clique problem

DOI10.1088/1742-5468/AACE2CMaRDI QIDQ3303299zbMATH OpenOpenAlexWikidataFDO

Authors Maria Chiara Angelini

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.05903

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The theoretical information threshold for the planted clique problem is $2lo{g}_2(N)$, however no polynomial algorithm is known to recover a planted clique of size $O(N^{1/2-epsilon})$, $epsilon>0$. In this paper we will apply a standard method for the analysis of disordered models, the Parallel-Tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the Sparse Planted Independent Set problem. In this situation thresholds should be sharper and finite size corrections should be less important. Also in this case PT shows a polynomial scaling in the hard region for the recovery.

Recommendations

• A new approach to the planted clique problem
• Algorithm for relatively small planted clique with small edge probability
• Some spin glass ideas applied to the clique problem
• Reconstruction and estimation in the planted partition model
• Phase transitions for the cavity approach to the clique problem on random graphs

Cites work

• scientific article; zbMATH DE number 3564899 (Why is no real title available?)
• scientific article; zbMATH DE number 3333197 (Why is no real title available?)
• Cliques in random graphs
• Community detection in dense random networks
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Computational barriers in minimax submatrix detection
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding one community in a sparse graph
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Statistical mechanics of the vertex-cover problem

Cited in

(3)

• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model

This page was built for publication: Parallel tempering for the planted clique problem

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