%0 Journal Article %1 ISI:000312963100022 %A Zhang, Pan %A Krzakala, Florent %A Reichardt, Joerg %A Zdeborova, Lenka %C TEMPLE CIRCUS, TEMPLE WAY, BRISTOL BS1 6BE, ENGLAND %D 2012 %I IOP PUBLISHING LTD %J JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT %K algorithms analysis clustering inference iscpif message-passing of statistical techniques %R 10.1088/1742-5468/2012/12/P12021 %T Comparative study for inference of hidden classes in stochastic block models %X Inference of hidden classes in stochastic block models is a classical problem with important applications. Most commonly used methods for this problem involve naive mean field approaches or heuristic spectral methods. Recently, belief propagation was proposed for this problem. In this contribution we perform a comparative study between the three methods on synthetically created networks. We show that belief propagation shows much better performance when compared to naive mean field and spectral approaches. This applies to accuracy, computational efficiency and the tendency to overfit the data.

@article{ISI:000312963100022, abstract = {{Inference of hidden classes in stochastic block models is a classical problem with important applications. Most commonly used methods for this problem involve naive mean field approaches or heuristic spectral methods. Recently, belief propagation was proposed for this problem. In this contribution we perform a comparative study between the three methods on synthetically created networks. We show that belief propagation shows much better performance when compared to naive mean field and spectral approaches. This applies to accuracy, computational efficiency and the tendency to overfit the data.}}, added-at = {2015-05-15T21:46:32.000+0200}, address = {{TEMPLE CIRCUS, TEMPLE WAY, BRISTOL BS1 6BE, ENGLAND}}, affiliation = {{Zhang, P (Reprint Author), CNRS, 10 Rue Vauquelin, F-75005 Paris, France. Zhang, Pan; Krzakala, Florent, CNRS, F-75005 Paris, France. Zhang, Pan; Krzakala, Florent, ESPCI ParisTech, UMR Gulliver 7083, F-75005 Paris, France. Reichardt, Joerg, Univ Wurzburg, Inst Theoret Phys, D-97074 Wurzburg, Germany. Zdeborova, Lenka, CEA Saclay, Inst Phys Theor, IPhT, F-91191 Gif Sur Yvette, France. Zdeborova, Lenka, CENS, Lab Leon Brillouin, CNRS, URA 2306, F-91191 Gif Sur Yvette, France.}}, article-number = {{P12021}}, author = {Zhang, Pan and Krzakala, Florent and Reichardt, Joerg and Zdeborova, Lenka}, author-email = {{pan.zhang@espci.fr fk@espci.fr reichardt@physik.uni-wuerzburg.de lenka.zdeborova@gmail.com}}, biburl = {https://www.bibsonomy.org/bibtex/256edde3e8dfdd9e7e6d658b3f7d9adfa/iscpif}, cited-references = {{Daudin JJ, 2008, STAT COMPUT, V18, P173, DOI 10.1007/s11222-007-9046-7. Decelle A, 2011, PHYS REV E, V84, DOI 10.1103/PhysRevE.84.066106. Decelle A, 2011, PHYS REV LETT, V107, DOI 10.1103/PhysRevLett.107.065701. DEMPSTER AP, 1977, J ROY STAT SOC B MET, V39, P1. Easley D., 2010, NETWORKS CROWDS MARK. Goldenberg A., 2009, FDN TRENDS MACH LEAR, V2, P1. Hastings MB, 2006, PHYS REV E, V74, DOI 10.1103/PhysRevE.74.035102. Hofman JM, 2008, PHYS REV LETT, V100, DOI 10.1103/PhysRevLett.100.258701. HOLLAND PW, 1983, SOC NETWORKS, V5, P109, DOI 10.1016/0378-8733(83)90021-7. Karlis D, 2003, COMPUT STAT DATA AN, V41, P577, DOI 10.1016/S0167-9473(02)00177-9. Lafon S, 2006, IEEE T PATTERN ANAL, V28, P1393, DOI 10.1109/TPAMI.2006.184. Mossel E, 2012, ARXIV12021499V3. Nadakuditi RR, 2012, PHYS REV LETT, V108, DOI 10.1103/PhysRevLett.108.188701. Neal RM, 1998, NATO ADV SCI I D-BEH, V89, P355. Newman MEJ, 2004, PHYS REV E, V69, DOI 10.1103/PhysRevE.69.026113. Newman MEJ, 2010, COMPLEX NETWORKS INT. Newman MEJ, 2006, PHYS REV E, V74, DOI 10.1103/PhysRevE.74.036104. Onsjo M, 2006, LNCS, V4228, P507. Pinkert S, 2010, PLOS COMPUT BIOL, V6, DOI 10.1371/journal.pcbi.1000659. Reichardt J, 2011, PLOS ONE, V6, DOI 10.1371/journal.pone.0021282. Reichardt J, 2008, PHYS REV LETT, V101, DOI 10.1103/PhysRevLett.101.078701. Sen P., 2007, CSTR4858 U MAR. Uetz P, 2000, NATURE, V403, P623. Weiss Y, 2001, ADV MEAN FIELD METHO, P229. Wellman B, 2001, SCIENCE, V293, P2031, DOI 10.1126/science.1065547. Yedidia JS, 2001, 2001 IJCAI INT JOINT.}}, doc-delivery-number = {{062ZG}}, doi = {{10.1088/1742-5468/2012/12/P12021}}, funding-acknowledgement = {{Projet DIM `problematique transversales aux systemes complexes' of the Institut des Systemes Complexes, Paris Ile-de-France (ISC-PIF); Fellowship Computational Sciences of the Volkswagen Foundation}}, funding-text = {{We wish to thank to Cris Moore for discussions about various aspects of the EM BP algorithm. This work was supported by the Projet DIM `problematique transversales aux systemes complexes' of the Institut des Systemes Complexes, Paris Ile-de-France (ISC-PIF). JR was supported by a Fellowship Computational Sciences of the Volkswagen Foundation.}}, interhash = {47b10f9d080fb1ceaf29c626c8eeee9c}, intrahash = {56edde3e8dfdd9e7e6d658b3f7d9adfa}, issn = {{1742-5468}}, journal = {{JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT}}, journal-iso = {{J. Stat. Mech.-Theory Exp.}}, keywords = {algorithms analysis clustering inference iscpif message-passing of statistical techniques}, keywords-plus = {{EM ALGORITHM; NETWORKS}}, language = {{English}}, month = {{DEC}}, number-of-cited-references = {{26}}, publisher = {{IOP PUBLISHING LTD}}, research-areas = {{Mechanics; Physics}}, researcherid-numbers = {{Zdeborova, Lenka/B-9999-2014}}, times-cited = {{4}}, timestamp = {2015-06-05T00:17:30.000+0200}, title = {{Comparative study for inference of hidden classes in stochastic block models}}, type = {{Article}}, unique-id = {{ISI:000312963100022}}, web-of-science-categories = {{Mechanics; Physics, Mathematical}}, year = 2012 }