Finding Hidden Cliques of Size \(\sqrt{N/e}\) in Nearly Linear Time
Consider an ErdsRenyi random graph in which each edge is present independently with probability \(1/2\), except for a subset \(\mathsf{C}_N\) of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm ofDekel et al. (ANALCO. SIAM, pp 6775, 2011) provably identifies the clique \(\mathsf{C}_N\) in linear time, provided \(|\mathsf{C}_N|\ge 1.261\sqrt{N}\). Spectral methods can be shown to fail on cliques smaller than \(\sqrt{N}\). In this paper we describe a nearly linear-time algorithm that succeeds with high probability for \(|\mathsf{C}_N|\ge (1+{\varepsilon })\sqrt{N/e}\) for any \({\varepsilon }>0\). This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on \(N\) vertices). For large-girth regular graphs of degree \((\varDelta +1)\) we prove that so-called local algorithms succeed if \(|\mathsf{C}_N|\ge (1+{\varepsilon })N/\sqrt{e\varDelta }\) and fail if \(|\mathsf{C}_N|\le (1-{\varepsilon })N/\sqrt{e\varDelta }\).
random graphs local algorithms average case complexity approximate message passing belief propagation sparse recovery primary: 68q87 secondary: 68q25 97k50