Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives

References

• Fortunato , S . 2010 . Phys. Rep. , 486 : 75
   Web of Science ®Google Scholar
• Rosvall , M and Bergstrom , C . 2008 . Proc. Natl. Acad. Sci. USA , 105 : 1118
   PubMed Web of Science ®Google Scholar
• Radicchi , F , Castellano , C , Cecconi , F , Loreto , V and Parisi , D . 2004 . Proc. Natl. Acad. Sci. USA , 101 : 2658
   PubMed Web of Science ®Google Scholar
• Lancichinetti , A , Radicchi , F and Ramasco , J . 2010 . Phys. Rev. E , 81 : 046110
   Web of Science ®Google Scholar
• Blondel , V , Guillaume , J , Lambiotte , R and Lefebvre , E . 2008 . J. Stat. Mech. , : 10008
   Web of Science ®Google Scholar
• Gregory , S . 2010 . New J. Phys. , 12 : 103018
   Web of Science ®Google Scholar
• Duch , J and Arenas , A . 2005 . Phys. Rev. E , 72 : 027104
   Web of Science ®Google Scholar
• Newman , MEJ and Girvan , M . 2004 . Phys. Rev. E , 69 : 026113
   PubMed Web of Science ®Google Scholar
• Girvan , M and Newman , MEJ . 2002 . Proc. Natl. Acad. Sci. USA , 99 : 7821
   PubMed Web of Science ®Google Scholar
• Ronhovde , P and Nussinov , Z . 2010 . Phys. Rev. E , 81 : 046114
   Web of Science ®Google Scholar
• Ronhovde , P and Nussinov , Z . 2009 . Phys. Rev. E , 80 : 016109
   Web of Science ®Google Scholar
• Reichardt , J and Bornholdt , S . 2006 . Phys. Rev. E , 74 : 016110
   PubMed Web of Science ®Google Scholar
• Gudkov , V , Montealegre , V , Nussinov , S and Nussinov , Z . 2008 . Phys. Rev. E , 78 : 016113
   Web of Science ®Google Scholar
• Hastings , M . 2006 . Phys. Rev. E , 74 : 035102 (R)
   Web of Science ®Google Scholar
• J. Šíma and S. Schaeffer, On the NP-completeness of some graph cluster measures, in J. Wiedermann, G. Tel, J. Pokorný, M. Bieliková and J. Štuller, eds., Proceedings of the Thirty-second International Conference on Current Trends in Theory and Practice of Computer Science (Sofsem 06), Lecture Notes in Computer Science, Vol. 3831 (2006), p.530
   Google Scholar
• Bayati , M , Borgs , C , Braunstein , A , Chayes , J , Ramezanpour , A and Zecchina , R . 2008 . Phys. Rev. Lett. , 101 : 037208
   Web of Science ®Google Scholar
• Zhou , J and Zhou , H . 2009 . Phys. Rev. E , 79 : 020103(R)
   Google Scholar
• Nishimori , H and Wong , KYM . 1999 . Phys. Rev. E , 60 : 132
   PubMed Web of Science ®Google Scholar
• Monasson , R , Zecchina , R , Kirkpatrick , S , Selman , B and Troyansky , L . 1999 . Nature , 400 : 133
   Web of Science ®Google Scholar
• Mézard , M , Parisi , G and Zecchina , R . 2002 . Science , 297 : 812
   PubMed Web of Science ®Google Scholar
• F. Krzakala and L. Zdeborová, J. Phys.: Conf. Series 95 (2008) 012012
   Google Scholar
• Hogg , T , Huberman , B and Williams , C . 1996 . Artif. Intell. , 81 : 1
   Web of Science ®Google Scholar
• Good , B , de Montjoye , Y and Clauset , A . 2010 . Phys. Rev. E , 81 : 046106
   Web of Science ®Google Scholar
• Mézard , M , Parisi , G and Virasoro , M . 1986 . Spin Glass Theory and Beyond, Lecture Notes in Physics , Vol. 9 , Singapore : World Scientific .
   Google Scholar
• Braunstein , A , Mézard , M and Zecchina , R . 2005 . Random Struct. Algorith. , 27 : 201
   Web of Science ®Google Scholar
• Gallager , R . 1963 . Low Density Parity Check Codes , Cambridge , MA : MIT Press .
   Google Scholar
• J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, in Proceedings of the Second National Conference on Artificial Intelligence, AAAI-82, Pittsburgh, PA, AAAI Press, Menlo Park, CA. 1982, p.133
   Google Scholar
• D. Hu, P. Ronhovde and Z. Nussinov, A replica infer-ence approach to unsupervised multi-scale image segmentation. Available at http://arxiv.org/abs/1106.5793, 2011
   Google Scholar
• P. Ronhovde, S. Chakrabarty, D. Hu, M. Sahu, K.F. Kelton, N.A. Mauro, K.K. Sahu, and Z. Nussinov, Detecting hidden spatial and spatio-temporal structures in glasses and complex physical systems by multiresolution network clustering, Eur. J. of Phys. E 34 (2011) p.105
   Google Scholar
• P. Ronhovde, S. Chakrabarty, M. Sahu, K. Sahu, K. Kelton, N. Mauro and Z. Nussinov, Detection of hidden structures on all scales in amorphous materials and complex physical systems: basic no-tions and applications to networks, lattice systems, and glasses. Available at http://arxiv.org/pdf/1101.0008, 2011
   Google Scholar
• M. Mézard and G. Parisi, J. Statist. Phys. 111, (2003) p.1–34
   Google Scholar
• Reichardt , J and Leone , M . 2008 . Phys. Rev. Lett. , 101 : 078701
   Web of Science ®Google Scholar
• Reichardt , J . 2009 . Structure in Complex Networks, Lecture Notes in Physics , Vol. 766 , Berlin : Springer-Verlag .
   Google Scholar
• Allahverdyan , A , Ver Steeg , G and Galstyan , A . 2010 . Europhys. Lett. , 90 : 18002
   Google Scholar
• Lancichinetti , A , Fortunato , S and Radicchi , F . 2008 . Phys. Rev. E , 78 : 046110
   Web of Science ®Google Scholar
• Fortunato , S and Barthélemy , M . 2007 . Proc. Natl. Acad. Sci. USA , 104 : 36
   PubMed Web of Science ®Google Scholar
• Kumpula , JM , Saramäki , J , Kaski , K and Kertész , J . 2007 . Eur. Phys. J. B , 56 : 41
   Web of Science ®Google Scholar
• Villain , J , Bidaux , R , Carton , JP and Conte , R . 1980 . J. Phys. (Paris) , 41 : 1263
   Google Scholar
• Shender , EF . 1982 . Sov. Phys. JETP , 56 : 178
   Google Scholar
• Henley , CL . 1989 . Phys. Rev. Lett. , 62 : 2056
   PubMed Web of Science ®Google Scholar
• Nussinov , Z , Biskup , M , Chayes , L and van den Brink , J . 2004 . Europhysics Lett. , 67 : 990
   Google Scholar
• Jonason , K , Vincent , E , Hammann , J , Bouchaud , J and Nordblad , P . 1998 . Phys. Rev. Lett. , 81 : 3243
   Web of Science ®Google Scholar
• Jonason , K , Nordblad , P , Vincent , E , Hammann , J and Bouchaud , J . 2000 . Eur. Phys. J. B , 13 : 99
   Web of Science ®Google Scholar
• Foster , D , Foster , J , Paczuski , M and Grassberger , P . 2010 . Phys. Rev. E , 81 : 046115
   Web of Science ®Google Scholar
• Stariolo , D , Montemurro , M and Tamarit , F . 2003 . Eur. Phys. J. B , 32 : 361
   Web of Science ®Google Scholar
• Berthier , L and Young , A . 2004 . Phys. Rev. B , 69 : 184423
   Web of Science ®Google Scholar
• U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski and D. Wagner, Maximizing modularity is hard. Available at http://arxiv.org/pdf/physics/0608255, 2006
   Google Scholar
• Cook , S . 1971 . “ The complexity of theorem proving procedures ” . In in Proceedings of Third Annual ACM Symposium on the Theory of Computing , Edited by: Grefenstette , J.J. 151 New York : ACM .
   Google Scholar
• Lubchenko , V and Wolynes , P . 2006 . Ann. Rev. Phys. Chem. , 58 : 235
   Web of Science ®Google Scholar
• Ricci-Tersenghi , F . 2010 . Science , 330 : 1639
   PubMed Web of Science ®Google Scholar
• Arenas , A , Díaz-Guilera , A and Pérez-Vicente , C . 2006 . Phys. Rev. Lett. , 96 : 114102
   PubMed Web of Science ®Google Scholar
• S.H. Strogatz, Nonlinear Dynamics and Chaos, Westview Press, Cambridge, 1994
   Google Scholar
• Fisher , D and Huse , D . 1998 . Phys. Rev. B , 38 : 386
   Web of Science ®Google Scholar
• Bray , A and Moore , M . 1987 . Phys. Rev. Lett. , 58 : 57
   PubMed Web of Science ®Google Scholar
• C. Thomas, D. Huse and A. Middleton, Chaos and universality in two-dimensional Ising spin glasses. Available at http://arxiv.org/abs/1012.3444v1, 2010
   Google Scholar
• Parisi , G . 1988 . Statistical Field Theory , New York : Addison-Wesley .
   Google Scholar
• Zinn-Justin , J . 2002 . Quantum Field Theory and Critical Phenomena , New York : Oxford University Press .
   Google Scholar
• Biroli , G , Chamon , C and Zamponi , F . 2008 . Phys. Rev. B , 78 : 224306
   Web of Science ®Google Scholar
• D. Hu, P. Ronhovde and Z. Nussinov, Phase transition in the com-munity detection problem: spin-glass type and dynamic perspectives. Available at http://arxiv.org/abs/1008.2699, 2010
   Google Scholar
• A. Decelle, F. Krzakala, C. Moore and L. Zdeborov´, Phys. Rev. Lett. 107 (2011) 065701, (earlier version available at http://arxiv.org/abs/1102.1182, 2011)
   Google Scholar
• Kirkpatrick , S , Gelatt , CD and Vecchi , MP . 1983 . Science , 220 : 4598
   Web of Science ®Google Scholar
• P.W. Kasteleyn and C.M. Fortuin, J. Phys. Soc. Jpn. 26 (Suppl.) (1969) p.11
   Google Scholar
• M.T. Mercaldo, J-Ch. Anglés d'Auriac and F. Iglói, Phys. Rev. E 69 (2004), article no. 056112
   Google Scholar
• J-Ch. Anglés d'Auriac, F. Iglói, M. Preissmann and A. Sebö, J. Phys. A: Math. Gen. 35 (2002) p.6973
   Google Scholar
• R. Juhász, H. Rieger and F. Iglói, Phys. Rev. E 64 (2001), article no. 056122
   Google Scholar