%0 Book Section %1 statphys23_0651 %A Iovanella, A. %A Scoppola, B. %A Scoppola, E. %A Viale, M. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K cavity clique combinatorial disordered field optimization problem statphys23 systems topic-9 %T Some spin glass ideas applied to the clique problem %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=651 %X We face the clique problem, i.e., the study of the maximal complete subgraph of a given graph $G$, by using ideas inspired by the cavity method introduced in spin glass theory. To this purpose we introduce an algorithm, which is sufficiently simple so that its behavior can be studied at least on random graphs providing some explanation of the difficulty of the problem. The algorithm is actually a Markov Chain Monte Carlo (MCMC), whose stationary measure is concentrated, for low temperature, on the cliques of the graph. The two particular features of this approach are the fact that the evolution can be thought as a probabilistic cellular automaton with mean field interaction, and therefore the configuration of the system may change completely even in a single step, and the fact that the dynamics is conservative. The algorithm has been tested on random graphs and on DIMACS benchmarks, with very good numerical results, also on large graphs. The rigorous study of the mixing time of the chain is still open.

@incollection{statphys23_0651, abstract = {We face the clique problem, i.e., the study of the maximal complete subgraph of a given graph $G$, by using ideas inspired by the cavity method introduced in spin glass theory. To this purpose we introduce an algorithm, which is sufficiently simple so that its behavior can be studied at least on random graphs providing some explanation of the difficulty of the problem. The algorithm is actually a Markov Chain Monte Carlo (MCMC), whose stationary measure is concentrated, for low temperature, on the cliques of the graph. The two particular features of this approach are the fact that the evolution can be thought as a probabilistic cellular automaton with mean field interaction, and therefore the configuration of the system may change completely even in a single step, and the fact that the dynamics is conservative. The algorithm has been tested on random graphs and on DIMACS benchmarks, with very good numerical results, also on large graphs. The rigorous study of the mixing time of the chain is still open.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Iovanella, A. and Scoppola, B. and Scoppola, E. and Viale, M.}, biburl = {https://www.bibsonomy.org/bibtex/2a71256e89c00a1bdc5b42c107ad12131/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {d7dc47815d84e9640bd6aa4c8182353e}, intrahash = {a71256e89c00a1bdc5b42c107ad12131}, keywords = {cavity clique combinatorial disordered field optimization problem statphys23 systems topic-9}, month = {9-13 July}, timestamp = {2007-06-20T10:16:25.000+0200}, title = {Some spin glass ideas applied to the clique problem}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=651}, year = 2007 }