{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:57:53Z","timestamp":1781326673195,"version":"3.54.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>\n                    Overlapping communities are pervasive in real-world networks, where vertices often participate in multiple communities simultaneously. The\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique percolation community (KCPC) model represents a fundamental paradigm for mining overlapping communities. However, existing KCPC mining methods are often hampered by inefficiency and scalability challenges, hindering their applicability to large-scale networks. To address these challenges, we propose several novel and efficient approaches for KCPC mining from perspectives of maximal cliques and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -cliques. Specifically, we first present a novel concept, termed Quasi-KCPC, which represents an incomplete KCPC and can be efficiently obtained as a byproduct during the maximal clique enumeration procedure. Based on Quasi-KCPC, we first propose a maximal clique enumeration-based solution that builds upon existing maximal clique adjacency graph traversal methods, but achieves improved efficiency by using Quasi-KCPC to dramatically reduce the scale of the maximal clique adjacency graph. Additionally, we propose a novel\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique listing-based solution, which adopts a different strategy: it first enumerates (k-1)-cliques and then connects the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -cliques sharing these (k-1)-cliques into KCPC. Our method further improves efficiency by shifting the connection target from\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -cliques to maximal cliques and employing Quasi-KCPC to significantly prune the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique enumeration tree. We also propose update algorithms for KCPC to handle dynamic addition and deletion of vertices and edges, enabling real-time analysis of KCPC. Extensive experiments on 12 large real-world graphs demonstrate the superiority of our algorithms, which can be up to two orders of magnitude faster than existing state-of-the-art solutions in KCPC mining, and almost two orders of magnitude faster than recomputation strategy in dynamic KCPC updates.\n                  <\/jats:p>","DOI":"10.1145\/3749181","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["Scaling Up k-Clique Percolation Community Detection"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4503-0361","authenticated-orcid":false,"given":"Yue","family":"Zeng","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"The University of Auckland, Auckland, New Zealand"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3105-5325","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4364-0633","authenticated-orcid":false,"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTEL.2016.7881885"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl039"},{"key":"e_1_2_1_3_1","volume-title":"Conference on Learning Theory. PMLR, 383-416","author":"Banks Jess","year":"2016","unstructured":"Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. 2016. Information-theoretic thresholds for community detection in sparse networks. In Conference on Learning Theory. PMLR, 383-416."},{"key":"e_1_2_1_4_1","volume-title":"An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-95408-6_9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00241"},{"key":"e_1_2_1_8_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_10_1","volume-title":"Clique percolation in random networks. Physical review letters","author":"Der\u00e9nyi Imre","year":"2005","unstructured":"Imre Der\u00e9nyi, Gergely Palla, and Tam\u00e1s Vicsek. 2005. Clique percolation in random networks. Physical review letters, Vol. 94, 16 (2005), 160202."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.97.052133"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_14_1","first-page":"3","article-title":"Listing all maximal cliques in large sparse real-world graphs","volume":"18","author":"Eppstein David","year":"2013","unstructured":"David Eppstein, Maarten L\u00f6ffler, and Darren Strash. 2013. Listing all maximal cliques in large sparse real-world graphs. Journal of Experimental Algorithmics (JEA), Vol. 18 (2013), 3-1.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_15_1","volume-title":"Line graphs, link partitions, and overlapping communities. Physical review E","author":"Evans Tim S","year":"2009","unstructured":"Tim S Evans and Renaud Lambiotte. 2009. Line graphs, link partitions, and overlapping communities. Physical review E, Vol. 80, 1 (2009), 016105."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/107\/28005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/180"},{"key":"e_1_2_1_18_1","volume-title":"2019 IEEE International Conference on Big Data (Big Data). IEEE, 4773-4782","author":"Motaleb Faysal Md Abdul","year":"2019","unstructured":"Md Abdul Motaleb Faysal and Shaikh Arifuzzaman. 2019. Distributed community detection in large networks using an information-theoretic approach. In 2019 IEEE International Conference on Big Data (Big Data). IEEE, 4773-4782."},{"key":"e_1_2_1_19_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3-5 (2010), 75-174."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.229"},{"key":"e_1_2_1_22_1","volume-title":"FLIP-CPM: A Parallel Community Detection Method. In Computer and Information Sciences II: 26th International Symposium on Computer and Information Sciences. Springer, 249-255","author":"Gregori Enrico","year":"2012","unstructured":"Enrico Gregori, Luciano Lenzini, Simone Mainardi, and Chiara Orsini. 2012b. FLIP-CPM: A Parallel Community Detection Method. In Computer and Information Sciences II: 26th International Symposium on Computer and Information Sciences. Springer, 249-255."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCSW.2011.17"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-022-01704-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/tpj.16007"},{"key":"e_1_2_1_26_1","volume-title":"Overlapping community discovery for identifying key research themes","author":"Huang Lu","year":"2020","unstructured":"Lu Huang, Fangyan Liu, and Yi Zhang. 2020. Overlapping community discovery for identifying key research themes. IEEE transactions on engineering management, Vol. 68, 5 (2020), 1321-1333."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00132"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0379-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2008.0010"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.18520\/cs\/v118\/i1\/62-69"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_33_1","volume-title":"Sequential algorithm for fast clique percolation. Physical review E","author":"Kumpula Jussi M","year":"2008","unstructured":"Jussi M Kumpula, Mikko Kivel\u00e4, Kimmo Kaski, and Jari Saram\u00e4ki. 2008. Sequential algorithm for fast clique percolation. Physical review E, Vol. 78, 2 (2008), 026109."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.066118"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/jan.15787"},{"key":"e_1_2_1_36_1","volume-title":"Biclique communities. Physical review E","author":"Lehmann Sune","year":"2008","unstructured":"Sune Lehmann, Martin Schwartz, and Lars Kai Hansen. 2008. Biclique communities. Physical review E, Vol. 78, 1 (2008), 016108."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.042116"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2020.12.003"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_40_1","first-page":"3335","article-title":"I\/O-efficient algorithms for degeneracy computation on massive networks","volume":"34","author":"Li Rong-Hua","year":"2020","unstructured":"Rong-Hua Li, Qiushuo Song, Xiaokui Xiao, Lu Qin, Guoren Wang, Jeffrey Xu Yu, and Rui Mao. 2020b. I\/O-efficient algorithms for degeneracy computation on massive networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 7 (2020), 3335-3348.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2962751"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkab794"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2019.2926033"},{"key":"e_1_2_1_46_1","first-page":"664","volume-title":"Nature","volume":"446","author":"Palla Gergely","year":"2007","unstructured":"Gergely Palla, Albert-L\u00e1szl\u00f3 Barab\u00e1si, and Tam\u00e1s Vicsek. 2007a. Quantifying social group evolution. Nature, Vol. 446, 7136 (2007), 664-667."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_48_1","volume-title":"Directed network modules. New journal of physics","author":"Palla Gergely","year":"2007","unstructured":"Gergely Palla, Ill\u00e9s J Farkas, P\u00e9ter Pollner, Imre Der\u00e9nyi, and Tam\u00e1s Vicsek. 2007b. Directed network modules. New journal of physics, Vol. 9, 6 (2007), 186."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0255717"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-024-58256-8"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.54"},{"key":"e_1_2_1_52_1","volume-title":"Adrian Quintero, and Lisa Jamieson.","author":"Ribeiro Santiago Pedro Henrique","year":"2022","unstructured":"Pedro Henrique Ribeiro Santiago, Gustavo Hermes Soares, Adrian Quintero, and Lisa Jamieson. 2022. Comparing the Clique Percolation with other overlapping community detection algorithms in psychological networks: A Monte Carlo simulation study. (2022)."},{"key":"e_1_2_1_53_1","volume-title":"International Journal on Emerging Technologies","author":"Sathiyakumari K","year":"2020","unstructured":"K Sathiyakumari and MS Vijaya. 2020. Overlapping Community Structure Detection using Twitter Data. International Journal on Emerging Technologies (2020)."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77672-9_19"},{"key":"e_1_2_1_55_1","volume-title":"The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science","author":"Tomita Etsuji","year":"2006","unstructured":"Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science, Vol. 363, 1 (2006), 28-42."},{"key":"e_1_2_1_56_1","unstructured":"Ying-Wooi Wan Rami Al-Ouran Carl G Mangleburg Thanneer M Perumal Tom V Lee Katherine Allison Vivek Swarup Cory C Funk Chris Gaiteri Mariet Allen et al. 2020. Meta-analysis of the Alzheimer's disease human brain transcriptome and functional dissection in mouse models. Cell reports Vol. 32 2 (2020)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512167"},{"key":"e_1_2_1_59_1","volume-title":"Shianne Van Duzen, and Peter Ryser","author":"Ye Ziqi","year":"2024","unstructured":"Ziqi Ye, Yanmei Mu, Shianne Van Duzen, and Peter Ryser. 2024. Root and shoot phenology, architecture, and organ properties: an integrated trait network among 44 herbaceous wetland species. New Phytologist (2024)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00192"},{"key":"e_1_2_1_62_1","unstructured":"Yue Zeng Miao Qiao Rong-Hua Li Hongchao Qin and Guoren Wang. 2025. Scaling Up k-Clique Percolation Community Detection. (2025). https:\/\/github.com\/bruce1114\/kcpc\/blob\/main\/kcpc_fullversion.pdf"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2017.2749282"},{"key":"e_1_2_1_64_1","first-page":"1934","article-title":"DynaMo: Dynamic community detection by incrementally maximizing modularity","volume":"33","author":"Zhuang Di","year":"2019","unstructured":"Di Zhuang, J Morris Chang, and Mingchen Li. 2019. DynaMo: Dynamic community detection by incrementally maximizing modularity. IEEE Transactions on Knowledge and Data Engineering, Vol. 33, 5 (2019), 1934-1945.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:39:32Z","timestamp":1781325572000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749181"],"URL":"https:\/\/doi.org\/10.1145\/3749181","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}