{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:18Z","timestamp":1750309518095,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T00:00:00Z","timestamp":1736380800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U22B2017"],"award-info":[{"award-number":["U22B2017"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>Much of the complexity of social, biological, and engineering systems arises from the complicated interactions among the entities in the corresponding networks. A number of network analysis tools have been successfully used to discover latent structures termed communities in such networks. However, some communities with relatively weak structures can be difficult to uncover because they are obscured by other stronger connections. To cope with this situation, our previous work proposes an algorithm called HICODE to detect and amplify the dominant and hidden community structures. In this work, we conduct a comprehensive and systematic theoretical analysis on the impact of hidden community structure and the efficacy of the HICODE algorithm, as well as provide illustrations of the detection process and results. Specifically, we define a multi-layer stochastic block model and use this model to explain why the existence of hidden structure makes the detection of dominant structure harder than equivalent random noises, which can also explain why many community detection algorithms only focusing on the dominant structure do not work well as expected. We then provide theoretical analysis that the iterative reducing methods could help to enhance the discovery of hidden structure as well as the dominant structure in the multi-layer stochastic block model for the two cases of accurate and inaccurate detection. Finally, visual simulations and experimental results are presented to show the process of HICODE algorithm and the impact of different number of layers on the detection quality.<\/jats:p>","DOI":"10.1145\/3706111","type":"journal-article","created":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T11:25:11Z","timestamp":1733138711000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Structure Amplification on Multi-layer Stochastic Block Models"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7627-4604","authenticated-orcid":false,"given":"Kun","family":"He","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9099-2690","authenticated-orcid":false,"given":"Xiaodong","family":"Xin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-350X","authenticated-orcid":false,"given":"Jialu","family":"Bao","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4579-2083","authenticated-orcid":false,"given":"Meng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0666-3123","authenticated-orcid":false,"given":"Bart","family":"Selman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8681-6075","authenticated-orcid":false,"given":"John E.","family":"Hopcroft","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3242034"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/978-3-030-59267-7_31","volume-title":"Proceedings of the 16th International Conference on Theory and Applications of Models of Computation","volume":"12337","author":"Bao Jialu","year":"2020","unstructured":"Jialu Bao, Kun He, Xiaodong Xin, Bart Selman, and John E. Hopcroft. 2020. Hidden community detection on two-layer stochastic models: A theoretical perspective. In Proceedings of the 16th International Conference on Theory and Applications of Models of Computation, Vol. 12337, 365\u2013376."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.005"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.026132"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"D295","DOI":"10.1093\/nar\/gkq1234","article-title":"IsoBase: A database of functionally related proteins across PPI networks","volume":"39","author":"Daniel Park","year":"2010","unstructured":"Park Daniel, Singh Rohit, Baym Michael, Liao Chung-Shou, and Berger Bonnie. 2010. IsoBase: A database of functionally related proteins across PPI networks. Nucleic Acids Research 39 (2010), D295.","journal-title":"Nucleic Acids Research"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/P09008"},{"key":"e_1_3_2_11_2","first-page":"117","article-title":"Strong consistency, graph laplacians, and the stochastic block model","volume":"22","author":"Deng Shaofeng","year":"2021","unstructured":"Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. 2021. Strong consistency, graph laplacians, and the stochastic block model. Journal of Machine Learning Research 22, 117 (2021), 1\u201344.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1109\/ICDMW.2018.00068","volume-title":"Proceedings of the 2018 IEEE International Conference on Data Mining Workshops (ICDMW 18)","author":"Gong Chenxu","year":"2018","unstructured":"Chenxu Gong, Guoyin Wang, Jun Hu, Ming Liu, Li Liu, and Zihe Yang. 2018. Finding multi-granularity community structures in social networks based on significance of community partition. In Proceedings of the 2018 IEEE International Conference on Data Mining Workshops (ICDMW 18), 415\u2013421."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.10.019"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340708"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"Kun He Sucheta Soundarajan Xuezhi Cao John E. Hopcroft and Menglong Huang. 2015. Revealing multiple layers of hidden community structure in networks. arXiv: 1501.05700. Retrieved from 10.48550\/arXiv.1501.05700","DOI":"10.48550\/arXiv.1501.05700"},{"issue":"10","key":"e_1_3_2_17_2","first-page":"4318","article-title":"Contextual correlation preserving multiview featured graph clustering","volume":"50","author":"He Tiantian","year":"2019","unstructured":"Tiantian He, Yang Liu, Tobey H. Ko, Keith C. C. Chan, and Yew-Soon Ong. 2019. Contextual correlation preserving multiview featured graph clustering. IEEE Transactions on Cybernetics 50, 10 (2019), 4318\u20134331.","journal-title":"IEEE Transactions on Cybernetics"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623706"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"e_1_3_2_20_2","first-page":"3565","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition","author":"Li Chao","year":"2020","unstructured":"Chao Li, Yixiao Yang, Kun He, Stephen Lin, and John E. Hopcroft. 2020. Single image reflection removal through cascaded refinement. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, 3565\u20133574."},{"issue":"6","key":"e_1_3_2_21_2","first-page":"3716","article-title":"Fast Markov clustering algorithm based on belief dynamics","volume":"53","author":"Li Huijia","year":"2022","unstructured":"Huijia Li, Wenzhe Xu, Chenyang Qiu, and Jian Pei. 2022. Fast Markov clustering algorithm based on belief dynamics. IEEE Transactions on Cybernetics 53, 6 (2022), 3716\u20133725.","journal-title":"IEEE Transactions on Cybernetics"},{"key":"e_1_3_2_22_2","first-page":"512","volume-title":"Neurocomputing","author":"Li Hui-Jia","year":"2022","unstructured":"Hui-Jia Li, Shenpeng Song, Wenze Tan, Zhaoci Huang, Xiaoyan Li, Wenzhe Xu, and Jie Cao. 2022. Characterizing the fuzzy community structure in Link graph via the likelihood optimization. Neurocomputing 512 (2022), 482\u2013493."},{"issue":"2","key":"e_1_3_2_23_2","first-page":"1","article-title":"Measuring the network vulnerability based on Markov criticality","volume":"16","author":"Li Hui-Jia","year":"2021","unstructured":"Hui-Jia Li, Lin Wang, Zhan Bu, Jie Cao, and Yong Shi. 2021. Measuring the network vulnerability based on Markov criticality. ACM Transactions on Knowledge Discovery from Data 16, 2 (2021), 1\u201324.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/1718487.1718519","volume-title":"Proceedings of the 3rd International Conference on Web Search and Web Data Mining, (WSDM \u201910)","author":"Mislove Alan","year":"2010","unstructured":"Alan Mislove, Bimal Viswanath, Krishna P. Gummadi, and Peter Druschel. 2010. You are who you know: Inferring user profiles in online social networks. In Proceedings of the 3rd International Conference on Web Search and Web Data Mining, (WSDM \u201910), 251\u2013260."},{"issue":"2","key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/TCSS.2022.3162229","article-title":"Link prediction and unlink prediction on dynamic networks","volume":"10","author":"Muro Christina","year":"2022","unstructured":"Christina Muro, Boyu Li, and Kun He. 2022. Link prediction and unlink prediction on dynamic networks. IEEE Transactions on Computational Social Systems 10, 2 (2022), 590\u2013601.","journal-title":"IEEE Transactions on Computational Social Systems"},{"issue":"1","key":"e_1_3_2_26_2","first-page":"1","article-title":"Detecting intrinsic communities in evolving networks","volume":"9","author":"Nath Keshab","year":"2019","unstructured":"Keshab Nath and Swarup Roy. 2019. Detecting intrinsic communities in evolving networks. Social Network Analysis and Mining 9, 1 (2019), 1\u201315.","journal-title":"Social Network Analysis and Mining"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3424672"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_3_2_31_2","unstructured":"Daniel Salz Nicholas Benavides and Jonathan Li. 2019. Hidden community detection in online forums. CS224W: Machine Learning with Graphs (2019) 1\u201310. Retrieved from http:\/\/snap.stanford.edu\/class\/cs224w-2019\/project\/26424232.pdf"},{"key":"e_1_3_2_32_2","first-page":"147:1","article-title":"Local network community detection with continuous optimization of conductance and weighted kernel k-means","volume":"17","author":"Laarhoven Twan van","year":"2016","unstructured":"Twan van Laarhoven and Elena Marchiori. 2016. Local network community detection with continuous optimization of conductance and weighted kernel k-means. Journal of Machine Learning Research 17 (2016), 147:1\u2013147:28.","journal-title":"Journal of Machine Learning Research"},{"issue":"5","key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3567597","article-title":"Uncovering the local hidden community structure in social networks","volume":"17","author":"Wang Meng","year":"2023","unstructured":"Meng Wang, Boyu Li, Kun He, and John Hopcroft. 2023. Uncovering the local hidden community structure in social networks. ACM Transactions on Knowledge Discovery from Data 17, 5 (2023), 1\u201325.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706111","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3706111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:03Z","timestamp":1750295883000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,9]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3706111"],"URL":"https:\/\/doi.org\/10.1145\/3706111","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2025,1,9]]},"assertion":[{"value":"2023-03-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}