{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:44:49Z","timestamp":1760402689974,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:00:00Z","timestamp":1641168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>With the rapid expansion of graphs and networks and the growing magnitude of data from all areas of science, effective treatment and compression schemes of context-dependent data is extremely desirable. A particularly interesting direction is to compress the data while keeping the \u201cstructural information\u201d only and ignoring the concrete labelings. Under this direction, Choi and Szpankowski introduced the structures (unlabeled graphs) which allowed them to compute the structural entropy of the Erd\u0151s\u2013R\u00e9nyi random graph model. Moreover, they also provided an asymptotically optimal compression algorithm that (asymptotically) achieves this entropy limit and runs in expectation in linear time. In this paper, we consider the stochastic block models with an arbitrary number of parts. Indeed, we define a partitioned structural entropy for stochastic block models, which generalizes the structural entropy for unlabeled graphs and encodes the partition information as well. We then compute the partitioned structural entropy of the stochastic block models, and provide a compression scheme that asymptotically achieves this entropy limit.<\/jats:p>","DOI":"10.3390\/e24010081","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T22:51:50Z","timestamp":1641250310000},"page":"81","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Structural Entropy of the Stochastic Block Models"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2013-2962","authenticated-orcid":false,"given":"Jie","family":"Han","sequence":"first","affiliation":[{"name":"Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8991-6757","authenticated-orcid":false,"given":"Tao","family":"Guo","sequence":"additional","affiliation":[{"name":"Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9779-7225","authenticated-orcid":false,"given":"Qiaoqiao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Department of Computer Science, School of Computing, National University of Singapore, Singapore 11741, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0920-1357","authenticated-orcid":false,"given":"Wei","family":"Han","sequence":"additional","affiliation":[{"name":"Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4796-8249","authenticated-orcid":false,"given":"Bo","family":"Bai","sequence":"additional","affiliation":[{"name":"Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co., Ltd., Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,3]]},"reference":[{"key":"ref_1","unstructured":"Yeung, R.W. (2008). Information Theory and Network Coding, Springer."},{"key":"ref_2","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley-Interscience. [2nd ed.]."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical Theory of Communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1109\/TIT.1953.1188572","article-title":"The lattice theory of information","volume":"1","author":"Shannon","year":"1953","journal-title":"Trans. Ire Prof. Group Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1038\/nature03607","article-title":"Uncovering the overlapping community structure of complex networks in nature and society","volume":"435","author":"Palla","year":"2005","journal-title":"Nature"},{"key":"ref_6","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":"Social Netw."},{"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","unstructured":"Mossel, E., Neeman, J., and Sly, A. (2015, January 14\u201317). Consistency thresholds for the planted bisection model. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","DOI":"10.1145\/2746539.2746603"},{"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":"4729","DOI":"10.1109\/TIT.2017.2653804","article-title":"Information limits for recovering a hidden community","volume":"63","author":"Hajek","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"036114","DOI":"10.1103\/PhysRevE.79.036114","article-title":"Entropy of network ensembles","volume":"79","author":"Bianconi","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"056122","DOI":"10.1103\/PhysRevE.85.056122","article-title":"Entropy of stochastic blockmodel ensembles","volume":"85","author":"Peixoto","year":"2012","journal-title":"Phys. Rev. E"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","unstructured":"Asadi, A.R., Abbe, E., and Verd\u00fa, S. (2017, January 25\u201330). Compressing data on graphs with clusters. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8006796"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Zenil, H., Kiani, N.A., and Tegn\u00e9r, J. (2018). A Review of Graph and Network Complexity from an Algorithmic Information Perspective. Entropy, 20.","DOI":"10.3390\/e20080551"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","article-title":"On the succinct representation of graphs","volume":"8","year":"1984","journal-title":"Discr. Appl. Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Harary, F., and Palmer, E.M. (1973). Graphical Enumeration, Academic Press.","DOI":"10.1016\/B978-0-12-324245-7.50005-8"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0166-218X(90)90011-Z","article-title":"Succinct representation of general unlabeled graphs","volume":"28","author":"Naor","year":"1990","journal-title":"Discr. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kieffer, J.C., Yang, E.H., and Szpankowski, W. (July, January 28). Structural complexity of random binary trees. Proceedings of the 2009 IEEE International Symposium on Information Theory (ISIT), Seoul, Korea.","DOI":"10.1109\/ISIT.2009.5205704"},{"key":"ref_20","unstructured":"Adler, M., and Mitzenmacher, M. (2001, January 27\u201329). Towards compressing Web graphs. Proceedings of the DCC 2001. Data Compression Conference, Snowbird, Utah."},{"key":"ref_21","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., and Raghavan, P. (July, January 28). On Compressing Social Networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Peshkin, L. (2007, January 27\u201329). Structure induction by lossless graph compression. Proceedings of the 2007 Data Compression Conference (DCC\u201907), Snowbird, Utah.","DOI":"10.1109\/DCC.2007.73"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1425","DOI":"10.1109\/TIT.2004.830754","article-title":"Compression of words over a partially commutative alphabet","volume":"50","author":"Savari","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"06001","DOI":"10.1088\/1742-5468\/2008\/06\/P06001","article-title":"Graph Compression-Save Information by Exploiting Redundancy","volume":"2008","author":"Sun","year":"2008","journal-title":"J. Statist. Mechan. Theory Exper."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1109\/TIT.2011.2173710","article-title":"Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments","volume":"58","author":"Choi","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"\u0141uczak, T., Magner, A., and Szpankowski, W. (2019, January 7\u201312). Compression of Preferential Attachment Graphs. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849739"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1002\/rsa.20842","article-title":"Asymmetry and structural information in preferential attachment graphs","volume":"55","author":"Magner","year":"2019","journal-title":"Random Struct. Algorithms"},{"key":"ref_28","unstructured":"Sauerhoff, M. (2021, November 01). On the Entropy of Models for the Web Graph. Available online: https:\/\/www.researchgate.net\/publication\/255589046OntheEntropyofModelsfortheWebGraph."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kontoyiannis, I., Lim, Y.H., Papakonstantinopoulou, K., and Szpankowski, W. (2021, January 11\u201316). Symmetry and the Entropy of Small-World Structures and Graphs. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Victoria, Australia.","DOI":"10.1109\/ISIT45174.2021.9517996"},{"key":"ref_30","unstructured":"K\u00f6rner, J. (1973). Coding of an information source having ambiguous alphabet and the entropy of graphs. 6th Prague Conference on Information Theory, Walter de Gruyter."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1109\/18.532875","article-title":"Source coding and graph entropies","volume":"42","author":"Alon","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02477860","article-title":"Life information theory and topology","volume":"17","author":"Rashevsky","year":"1955","journal-title":"Bull. Math. Biophys."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02477836","article-title":"A note on the information content of graphs","volume":"18","author":"Trucco","year":"1956","journal-title":"Bull. Math. Biophys."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02476948","article-title":"Entropy and the complexity of the graphs I: An index of the relative complexity of a graph","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02476692","article-title":"Entropy and the complexity of graphs II: The information content of digraphs and infinite graphs","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02476603","article-title":"Entropy and the complexity of graphs III: Graphs with prescribed information content","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF02476673","article-title":"Entropy and the complexity of graphs IV: Entropy measures and graphical structure","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"559","DOI":"10.3390\/e14030559","article-title":"Entropy and the Complexity of Graphs Revisited","volume":"14","author":"Mowshowitz","year":"2012","journal-title":"Entropy"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ins.2010.08.041","article-title":"A History of Graph Entropy Measures","volume":"181","author":"Dehmer","year":"2011","journal-title":"Inf. Sci."},{"key":"ref_40","unstructured":"Pasco, R.C. (1976). Source Coding Algorithms for Fast Data Compression. [Ph.D. Thesis, Stanford University]."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.203.0198","article-title":"Generalized Kraft Inequality and Arithmetic Coding","volume":"20","author":"Rissanen","year":"1976","journal-title":"IBM J. Res. Dev."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: Basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/81\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:59:57Z","timestamp":1760363997000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,3]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010081"],"URL":"https:\/\/doi.org\/10.3390\/e24010081","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,1,3]]}}}