text: We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for ( _ in - _ out > _ out e ) and fail for ( _ in - _ out < _ out e ) (with ( _ in ), ( _ out ) the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for ( _ in - _ out < _ out e ).
  @cite_42: In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.
  @cite_22: Phase transitions in spin-glass type systems and, more recently, in related computational problems have gained broad interest in disparate arenas. In the current work, we focus on the “community detection” problem when cast in terms of a general Potts spin-glass type problem. As such, our results apply to rather broad Potts spin-glass type systems. Community detection describes the general problem of partitioning a complex system involving many elements into optimally decoupled “communities” of such elements. We report on phase transitions between solvable and unsolvable regimes. A solvable region may further split into “easy” and “hard” phases. Spin-glass type phase transitions appear at both low and high temperatures (or noise). Low-temperature transitions correspond to an “order by disorder” type effect wherein fluctuations render the system ordered or solvable. Separate transitions appear at higher temperatures into a disordered (or an unsolvable) phase. Different sorts of randomness lead to disparate...
  @cite_11: We give a rigorous proof of two phase transitions for a disordered statistical mechanics system used to define an algorithm to find large cliques inside Erdos random graphs. Such a system is a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory.
summary: Let us finally mention that the probability measure ) can be interpreted as the Boltzmann distribution for a system of @math particles on the graph @math , with fugacity @math , and interacting attractively (for @math ). Statistical mechanics analogies were previously exploited in @cite_42 @cite_11 . (See also @cite_22 for the general community detection problem.)