{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:50:19Z","timestamp":1760161819355,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T00:00:00Z","timestamp":1609545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61807021"],"award-info":[{"award-number":["61807021"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen Science and Technology Program","award":["KQTD20170810150821146"],"award-info":[{"award-number":["KQTD20170810150821146"]}]},{"name":"Innovation and Entrepreneurship Project for Overseas High-Level Talents of Shenzhen","award":["KQJSCX20180327144037831"],"award-info":[{"award-number":["KQJSCX20180327144037831"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we study the phase transition property of an Ising model defined on a special random graph\u2014the stochastic block model (SBM). Based on the Ising model, we propose a stochastic estimator to achieve the exact recovery for the SBM. The stochastic algorithm can be transformed into an optimization problem, which includes the special case of maximum likelihood and maximum modularity. Additionally, we give an unbiased convergent estimator for the model parameters of the SBM, which can be computed in constant time. Finally, we use metropolis sampling to realize the stochastic estimator and verify the phase transition phenomenon thfough experiments.<\/jats:p>","DOI":"10.3390\/e23010065","type":"journal-article","created":{"date-parts":[[2021,1,3]],"date-time":"2021-01-03T19:54:46Z","timestamp":1609703686000},"page":"65","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exact Recovery of Stochastic Block Model by Ising Model"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3907-9556","authenticated-orcid":false,"given":"Feng","family":"Zhao","sequence":"first","affiliation":[{"name":"Department of Electronics, Tsinghua University, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Ye","sequence":"additional","affiliation":[{"name":"Tsinghua Berkeley Shenzhen Institute, Berkeley, CA 94704, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shao-Lun","family":"Huang","sequence":"additional","affiliation":[{"name":"Tsinghua Berkeley Shenzhen Institute, Berkeley, CA 94704, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/j.im.2015.02.004","article-title":"Personalized recommendations based on time-weighted overlapping community detection","volume":"52","author":"Feng","year":"2015","journal-title":"Inf. Manag."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1016\/S0167-8191(00)00048-X","article-title":"Graph partitioning models for parallel computing","volume":"26","author":"Hendrickson","year":"2000","journal-title":"Parallel Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2366","DOI":"10.1038\/nprot.2007.324","article-title":"Integration of biological networks and gene expression data using Cytoscape","volume":"2","author":"Cline","year":"2007","journal-title":"Nat. Protoc."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: First steps","volume":"5","author":"Holland","year":"1983","journal-title":"Soc. Netw."},{"key":"ref_6","first-page":"6446","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","article-title":"Exact recovery in the stochastic block model","volume":"62","author":"Abbe","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1214\/16-EJP4185","article-title":"Consistency thresholds for the planted bisection model","volume":"21","author":"Mossel","year":"2016","journal-title":"Electron. J. Probab."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Abbe, E., and Sandon, C. (2015, January 17\u201320). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2015.47"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1198\/016214501753208735","article-title":"Estimation and prediction for stochastic blockstructures","volume":"96","author":"Nowicki","year":"2001","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF02980577","article-title":"Beitrag zur theorie des ferromagnetismus","volume":"31","author":"Ising","year":"1925","journal-title":"Z. F\u00fcr Phys."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ye, M. (2020). Exact recovery and sharp thresholds of Stochastic Ising Block Model. arXiv.","DOI":"10.1109\/TIT.2021.3117264"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2300","DOI":"10.1016\/j.physa.2010.01.042","article-title":"Detecting community structure in complex networks using simulated annealing with k-means algorithms","volume":"389","author":"Liu","year":"2010","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1017\/S0305004100027419","article-title":"Some generalized order-disorder transformations","volume":"Volume 48","author":"Potts","year":"1952","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"ref_16","unstructured":"Liu, L. (2017). On the Log Partition Function of Ising Model on Stochastic Block Model. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1805","DOI":"10.1214\/17-AOS1620","article-title":"Exact recovery in the Ising blockmodel","volume":"47","author":"Berthet","year":"2019","journal-title":"Ann. Stat."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5881","DOI":"10.1109\/TIT.2016.2600566","article-title":"Information recovery from pairwise measurements","volume":"62","author":"Chen","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2788","DOI":"10.1109\/TIT.2016.2546280","article-title":"Achieving exact cluster recovery threshold via semidefinite programming","volume":"62","author":"Hajek","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"944","DOI":"10.1109\/JSTSP.2018.2834874","article-title":"Community detection with side information: Exact recovery under the stochastic block model","volume":"12","author":"Saad","year":"2018","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"052315","DOI":"10.1103\/PhysRevE.94.052315","article-title":"Equivalence between modularity optimization and maximum likelihood methods for community detection","volume":"94","author":"Newman","year":"2016","journal-title":"Phys. Rev. E"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"He, J., Chen, D., and Sun, C. (2016, January 14\u201317). A fast simulated annealing strategy for community detection in complex networks. Proceedings of the 2016 2nd IEEE International Conference on Computer and Communications (ICCC), Chengdu, China.","DOI":"10.1109\/CompComm.2016.7925125"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","article-title":"Finding community structure in very large networks","volume":"70","author":"Clauset","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1006\/jcss.1998.1576","article-title":"What do we know about the Metropolis algorithm?","volume":"57","author":"Diaconis","year":"1998","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/biomet\/84.1.1","article-title":"Computational Complexity of Markov Chain Monte Carlo Methods for Finite Markov Random Fields","volume":"84","author":"Frigessi","year":"1997","journal-title":"Biometrika"},{"key":"ref_26","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1086\/224954","article-title":"A Method for Detecting Structure in Sociometric Data","volume":"76","author":"Holland","year":"1970","journal-title":"Am. J. Sociol."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/65\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:06:20Z","timestamp":1760159180000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,2]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["e23010065"],"URL":"https:\/\/doi.org\/10.3390\/e23010065","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,1,2]]}}}