Finding hidden cliques in linear time with high probability

DOI10.1017/S096354831300045XMaRDI QIDQ5414144zbMATH OpenWikidataFDO

Authors Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

Publication date 2 May 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

hidden cliquelinear time algorithmrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Abstract: We are given a graph $G$ with $n$ vertices, where a random subset of $k$ vertices has been made into a clique, and the remaining edges are chosen independently with probability $frac12$. This random graph model is denoted $G(n,frac12,k)$. The hidden clique problem is to design an algorithm that finds the $k$-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov uses spectral techniques to find the hidden clique with high probability when $k=csqrtn$ for a sufficiently large constant $c>0$. Recently, an algorithm that solves the same problem was proposed by Feige and Ron. It has the advantages of being simpler and more intuitive, and of an improved running time of $O(n^2)$. However, the analysis in the paper gives success probability of only $2/3$. In this paper we present a new algorithm for finding hidden cliques that both runs in time $O(n^2)$, and has a failure probability that is less than polynomially small.

Recommendations

• Finding hidden cliques in linear time with high probability
• Finding hidden cliques in linear time
• scientific article; zbMATH DE number 1303602
• scientific article; zbMATH DE number 1380608
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time

Cites work

• Expected complexity of graph partitioning problems
• Finding and certifying a large hidden clique in a semirandom graph
• Hiding cliques for cryptographic security
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Probabilistic checking of proofs
• Probability. Theory and examples.
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Weighted sums of certain dependent random variables

Cited in

(35)

• Convex optimization for the densest subgraph and densest submatrix problems
• A simple spectral algorithm for recovering planted partitions
• Tensor clustering with planted structures: statistical optimality and computational limits
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Community detection in dense random networks
• Finding hidden cliques in linear time
• Finding dense subgraphs in \(G(n,1/2)\)
• Optimal detection of sparse principal components in high dimension
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• A Simple SVD Algorithm for Finding Hidden Partitions
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Finding and certifying a large hidden clique in a semirandom graph
• Finding a planted clique by adaptive probing
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Finding hidden cliques in linear time with high probability
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Cryptography from planted graphs: security with logarithmic-size messages
• How to hide a clique?
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• How to hide a clique?
• Maximum chordal subgraphs of random graphs
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Finding planted cliques using gradient descent
• Almost-linear planted cliques elude the Metropolis process
• Tensor factor model estimation by iterative projection
• Analysis of singular subspaces under random perturbations
• Is the space complexity of planted clique recovery the same as that of detection?
• Finding one community in a sparse graph
• Community detection in sparse random networks
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time

This page was built for publication: Finding hidden cliques in linear time with high probability

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