{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:06Z","timestamp":1787022366884,"version":"build-2736575974"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>Graph clustering and community detection are central problems in modern data mining. The increasing need for analyzing billion-scale data calls for faster and more scalable algorithms for these problems. There are certain trade-offs between the quality and speed of such clustering algorithms. In this paper, we design scalable algorithms that achieve high quality when evaluated based on ground truth.<\/jats:p>\n                  <jats:p>We develop a generalized sequential and shared-memory parallel framework based on the LAMBDACC objective (introduced by Veldt et al.), which encompasses modularity and correlation clustering. Our framework consists of highly-optimized implementations that scale to large data sets of billions of edges and that obtain high-quality clusters compared to ground-truth data, on both unweighted and weighted graphs. Our empirical evaluation shows that this framework improves the state-of-the-art trade-offs between speed and quality of scalable community detection. For example, on a 30-core machine with two-way hyper-threading, our implementations achieve orders of magnitude speedups over other correlation clustering baselines, and up to 28.44\u00d7 speedups over our own sequential baselines while maintaining or improving quality.<\/jats:p>","DOI":"10.14778\/3476249.3476282","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T12:46:23Z","timestamp":1635338783000},"page":"2305-2313","source":"Crossref","is-referenced-by-count":19,"title":["Scalable community detection via parallel correlation clustering"],"prefix":"10.14778","volume":"14","author":[{"given":"Jessica","family":"Shi","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eisenstat","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"\u0141\u0103cki","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Aggarwal and Haixun Wang","author":"Charu","year":"2010"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2992785"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400254"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_7_1","volume-title":"R-MAT: A Recursive Model for Graph Mining. In SIAM International Conference on Data Mining (SDM). 442--446","author":"Chakrabarti Deepayan","year":"2004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.139"},{"key":"e_1_2_1_10_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml Accessed on 07.27.2021.  Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml Accessed on 07.27.2021."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1611638.1611641"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2017.08.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.198"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380220"},{"key":"e_1_2_1_15_1","volume-title":"Large-scale Community Detection on Youtube for Topic Discovery and Exploration. In AAAI Conference on Weblogs and Social Media (ICWSM)","volume":"5","author":"Gargi Ullas","year":"2011"},{"key":"e_1_2_1_16_1","volume-title":"Distributed Louvain Algorithm for Graph Community Detection. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). 885--895","author":"Ghosh S."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_18_1","volume-title":"Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In International Conference on Machine Learning (ICML). 3887--3896","author":"Guo Ruiqi","year":"2020"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091047"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.012821"},{"key":"e_1_2_1_22_1","unstructured":"Biaobin Jiang Jiguang Wang Jingfa Xiao and Yong-Cui Wang. 2009. Gene Prioritization for Type 2 Diabetes in Tissue-Specific Protein Interaction Networks. Syst Biol 11.  Biaobin Jiang Jiguang Wang Jingfa Xiao and Yong-Cui Wang. 2009. Gene Prioritization for Type 2 Diabetes in Tissue-Specific Protein Interaction Networks. Syst Biol 11."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_24_1","unstructured":"Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data. Accessed on 07.27.2021.  Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data. Accessed on 07.27.2021."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.03.003"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.17706\/IJCEE.2016.8.3.207-218"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969249"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.59"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"U. Raghavan R. Albert and S. Kumara. 2007. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Phys. Rev. E Stat. Nonlin. Soft Matter Phys. 76 (2007).  U. Raghavan R. Albert and S. Kumara. 2007. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Phys. Rev. E Stat. Nonlin. Soft Matter Phys. 76 (2007).","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.016110"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.203"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963190.1970376"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"N. S. Sattar and S. Arifuzzaman. 2018. Parallelizing Louvain Algorithm: Distributed Memory Challenges. In IEEE Intl Conf on Dependable Autonomic and Secure Computing Intl Conf on Pervasive Intelligence and Computing Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC\/PiCom\/DataCom\/CyberSciTech). 695--701.  N. S. Sattar and S. Arifuzzaman. 2018. Parallelizing Louvain Algorithm: Distributed Memory Challenges. In IEEE Intl Conf on Dependable Autonomic and Secure Computing Intl Conf on Pervasive Intelligence and Computing Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC\/PiCom\/DataCom\/CyberSciTech). 695--701.","DOI":"10.1109\/DASC\/PiCom\/DataCom\/CyberSciTec.2018.00122"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2390633"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.032801"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-019-41695-z"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186110"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2015.11"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:03:11Z","timestamp":1672203791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476282"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476282","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}