{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:50Z","timestamp":1750309490110,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"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":["12071477, 71873137, and 72271232"],"award-info":[{"award-number":["12071477, 71873137, and 72271232"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MOE Project of Key Research Institute of Humanities and Social Sciences","award":["22JJD110001"],"award-info":[{"award-number":["22JJD110001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>\n            This paper proposes a distributed pseudo-likelihood method (DPL) to conveniently identify the community structure of large-scale networks. Specifically, we first propose a\n            <jats:italic>block-wise splitting<\/jats:italic>\n            method to divide large-scale network data into several subnetworks and distribute them among multiple workers. For simplicity, we assume the classical stochastic block model. Then, the DPL algorithm is iteratively implemented for the distributed optimization of the sum of the local pseudo-likelihood functions. At each iteration, the worker updates its local community labels and communicates with the master. The master then broadcasts the combined estimator to each worker for the new iterative steps. Based on the distributed system, DPL significantly reduces the computational complexity of the traditional pseudo-likelihood method using a single machine. Furthermore, to ensure statistical accuracy, we theoretically discuss the requirements of the worker sample size. Moreover, we extend the DPL method to estimate degree-corrected stochastic block models. The superior performance of the proposed distributed algorithm is demonstrated through extensive numerical studies and real data analysis.\n          <\/jats:p>","DOI":"10.1145\/3657300","type":"journal-article","created":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T15:46:18Z","timestamp":1713282378000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3943-655X","authenticated-orcid":false,"given":"Jiayi","family":"Deng","sequence":"first","affiliation":[{"name":"Department of Statistics and Epidemiology, Chinese PLA General Hospital, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4053-2680","authenticated-orcid":false,"given":"Danyang","family":"Huang","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0815-148X","authenticated-orcid":false,"given":"Bo","family":"Zhang","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing China"}]}],"member":"320","published-online":{"date-parts":[[2024,6,19]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.89"},{"key":"e_1_3_4_3_1","article-title":"Mixed membership stochastic blockmodels","volume":"21","author":"Airoldi Edo M.","year":"2008","unstructured":"Edo M. Airoldi, David Blei, Stephen Fienberg, and Eric Xing. 2008. Mixed membership stochastic blockmodels. Advances in Neural Information Processing Systems 21 (2008).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOS1138"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1545"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1587"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1290"},{"key":"e_1_3_4_8_1","first-page":"35","volume-title":"Conference on Learning Theory","author":"Chaudhuri Kamalika","year":"2012","unstructured":"Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. 2012. Spectral clustering of graphs with general degrees in the extended planted partition model. In Conference on Learning Theory. 35\u20131."},{"key":"e_1_3_4_9_1","article-title":"Communication-optimal distributed clustering","volume":"29","author":"Chen Jiecao","year":"2016","unstructured":"Jiecao Chen, He Sun, David Woodruff, and Qin Zhang. 2016. Communication-optimal distributed clustering. Advances in Neural Information Processing Systems 29 (2016).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2014.2307458"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.88"},{"key":"e_1_3_4_12_1","article-title":"Distributed high-dimensional regression under a quantile loss function","volume":"21","author":"Chen Xi","year":"2020","unstructured":"Xi Chen, Weidong Liu, Xiaojun Mao, and Zhuoyi Yang. 2020. Distributed high-dimensional regression under a quantile loss function. Journal of Machine Learning Research 21 (2020).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_4_13_1","first-page":"1","article-title":"First-order Newton-type estimator for distributed estimation and inference","author":"Chen Xi","year":"2021","unstructured":"Xi Chen, Weidong Liu, and Yichen Zhang. 2021. First-order Newton-type estimator for distributed estimation and inference. J. Amer. Statist. Assoc. (2021), 1\u201317.","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_3_4_14_1","first-page":"1655","article-title":"A split-and-conquer approach for analysis of extraordinarily large data","author":"Chen Xueying","year":"2014","unstructured":"Xueying Chen and Min-ge Xie. 2014. A split-and-conquer approach for analysis of extraordinarily large data. Statistica Sinica (2014), 1655\u20131684.","journal-title":"Statistica Sinica"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670322"},{"key":"e_1_3_4_16_1","article-title":"Subsampling spectral clustering for large-scale social networks","author":"Deng Jiayi","year":"2021","unstructured":"Jiayi Deng, Yi Ding, Yingqiu Zhu, Danyang Huang, Bingyi Jing, and Bo Zhang. 2021. Subsampling spectral clustering for large-scale social networks. arXiv preprint arXiv:2110.13613 (2021).","journal-title":"arXiv preprint arXiv:2110.13613"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asab007"},{"key":"e_1_3_4_18_1","first-page":"1","article-title":"Communication-efficient accurate statistical estimation","author":"Fan Jianqing","year":"2021","unstructured":"Jianqing Fan, Yongyi Guo, and Kaizheng Wang. 2021. Communication-efficient accurate statistical estimation. J. Amer. Statist. Assoc. (2021), 1\u201311.","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOS1713"},{"key":"e_1_3_4_20_1","first-page":"1203","volume-title":"International Conference on Machine Learning","author":"Garber Dan","year":"2017","unstructured":"Dan Garber, Ohad Shamir, and Nathan Srebro. 2017. Communication-efficient algorithms for distributed stochastic principal component analysis. In International Conference on Machine Learning. PMLR, 1203\u20131212."},{"key":"e_1_3_4_21_1","article-title":"On communication cost of distributed statistical estimation and dimensionality","volume":"27","author":"Garg Ankit","year":"2014","unstructured":"Ankit Garg, Tengyu Ma, and Huy Nguyen. 2014. On communication cost of distributed statistical estimation and dimensionality. Advances in Neural Information Processing Systems 27 (2014).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214502388618906"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2019.1637744"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1265"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/21-AOS2089"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2018.1429274"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.016107"},{"key":"e_1_3_4_31_1","article-title":"Communication-efficient sparse regression: A one-shot approach","author":"Lee Jason D.","year":"2015","unstructured":"Jason D. Lee, Yuekai Sun, Qiang Liu, and Jonathan E. Taylor. 2015. Communication-efficient sparse regression: A one-shot approach. arXiv preprint arXiv:1503.04337 (2015).","journal-title":"arXiv preprint arXiv:1503.04337"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1274"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2022.06.006"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2019.100629"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2020.1833888"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2305974"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2016.2634322"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12200"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2100482118"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.1938"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_4_42_1","article-title":"On spectral clustering: Analysis and an algorithm","volume":"14","author":"Ng Andrew","year":"2001","unstructured":"Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems 14 (2001).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2737600"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2014.988214"},{"key":"e_1_3_4_46_1","first-page":"1000","volume-title":"International Conference on Machine Learning","volume":"32","author":"Shamir Ohad","year":"2014","unstructured":"Ohad Shamir, Nati Srebro, and Tong Zhang. 2014. Communication-efficient distributed optimization using an approximate Newton-type method. In International Conference on Machine Learning, Vol. 32. PMLR, 1000\u20131008."},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_4_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.06.089"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364208"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOS1730"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_3_4_52_1","first-page":"3636","volume-title":"International Conference on Machine Learning","volume":"70","author":"Wang Jialei","year":"2017","unstructured":"Jialei Wang, Mladen Kolar, Nathan Srebro, and Tong Zhang. 2017. Efficient distributed learning with sparsity. In International Conference on Machine Learning, Vol. 70. PMLR, 3636\u20133645."},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2020.1730852"},{"key":"e_1_3_4_54_1","article-title":"Giant: Globally improved approximate Newton method for distributed optimization","volume":"31","author":"Wang Shusen","year":"2018","unstructured":"Shusen Wang, Fred Roosta, Peng Xu, and Michael W. Mahoney. 2018. Giant: Globally improved approximate Newton method for distributed optimization. Advances in Neural Information Processing Systems 31 (2018).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2023.107794"},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2700304"},{"key":"e_1_3_4_57_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9448"},{"key":"e_1_3_4_58_1","first-page":"504","volume-title":"International Conference on Machine Learning","author":"Yang Wenzhuo","year":"2015","unstructured":"Wenzhuo Yang and Huan Xu. 2015. A divide and conquer framework for distributed graph clustering. In International Conference on Machine Learning. PMLR, 504\u2013513."},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-36212-8_6"},{"key":"e_1_3_4_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2020.11.025"},{"key":"e_1_3_4_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2018.00044"},{"key":"e_1_3_4_62_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2022.2034636"},{"key":"e_1_3_4_63_1","article-title":"Distributed community detection in large networks","author":"Zhang Sheng","year":"2022","unstructured":"Sheng Zhang, Rui Song, Wenbin Lu, and Ji Zhu. 2022b. Distributed community detection in large networks. arXiv preprint arXiv:2203.06509 (2022).","journal-title":"arXiv preprint arXiv:2203.06509"},{"key":"e_1_3_4_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2018.2871673"},{"key":"e_1_3_4_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567769"},{"key":"e_1_3_4_66_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1006642108"},{"key":"e_1_3_4_67_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1036"},{"key":"e_1_3_4_68_1","first-page":"1","article-title":"Least-square approximation for a distributed system","author":"Zhu Xuening","year":"2021","unstructured":"Xuening Zhu, Feng Li, and Hansheng Wang. 2021. Least-square approximation for a distributed system. Journal of Computational and Graphical Statistics (2021), 1\u201315.","journal-title":"Journal of Computational and Graphical Statistics"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3657300","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3657300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:39Z","timestamp":1750295859000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3657300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":67,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1145\/3657300"],"URL":"https:\/\/doi.org\/10.1145\/3657300","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2024,6,19]]},"assertion":[{"value":"2023-02-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}