{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:17:12Z","timestamp":1779175032145,"version":"3.51.4"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T00:00:00Z","timestamp":1711411200000},"content-version":"vor","delay-in-days":14,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374, CCF-1845763"],"award-info":[{"award-number":["1122374, CCF-1845763"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0018947"],"award-info":[{"award-number":["DE-SC0018947"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR0011-18-3-0007"],"award-info":[{"award-number":["HR0011-18-3-0007"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Jump Center - SRC and DARPA"},{"DOI":"10.13039\/501100006374","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Nucleus decompositions have been shown to be a useful tool for finding dense subgraphs. The coreness value of a clique represents its density based on the number of other cliques it is adjacent to. One useful output of nucleus decomposition is to generate a hierarchy among dense subgraphs at different resolutions. However, existing parallel algorithms for nucleus decomposition do not generate this hierarchy, and only compute the coreness values. This paper presents a scalable parallel algorithm for hierarchy construction, with practical optimizations, such as interleaving the coreness computation with hierarchy construction and using a concurrent union-find data structure in an innovative way to generate the hierarchy. We also introduce a parallel approximation algorithm for nucleus decomposition, which achieves much lower span in theory and better performance in practice. We prove strong theoretical bounds on the work and span (parallel time) of our algorithms.<\/jats:p>\n          <jats:p>On a 30-core machine with two-way hyper-threading, our parallel hierarchy construction algorithm achieves up to a 58.84x speedup over the state-of-the-art sequential hierarchy construction algorithm by Sariyuce et al. and up to a 30.96x self-relative parallel speedup. On the same machine, our approximation algorithm achieves a 3.3x speedup over our exact algorithm, while generating coreness estimates with a multiplicative error of 1.33x on average.<\/jats:p>","DOI":"10.1145\/3639287","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Algorithms for Hierarchical Nucleus Decomposition"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4485-5492","authenticated-orcid":false,"given":"Jessica","family":"Shi","sequence":"first","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0685-064X","authenticated-orcid":false,"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, College Park, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6163-6625","authenticated-orcid":false,"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"11","article-title":"Truss-Based Community Search","volume":"10","author":"Akbas Esra","year":"2017","unstructured":"Esra Akbas and Peixiang Zhao. 2017. Truss-Based Community Search: A Truss-Equivalence Based Indexing Approach. Proc. VLDB Endow., Vol. 10, 11 (Aug. 2017), 1298--1309.","journal-title":"A Truss-Equivalence Based Indexing Approach. Proc. VLDB Endow."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933267.2933299"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-4-2"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433833"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916473"},{"key":"e_1_2_2_6_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. Brief Announcement: ParlayLib -- A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401971"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004264"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00090"},{"key":"e_1_2_2_12_1","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive Subgraphs for Social Network Analysis. National Security Agency Technical Report Vol. 16 3.1 (2008)."},{"key":"e_1_2_2_13_1","volume-title":"Dense Subgroup Identifying in Social Network. In International Conference on Advances in Social Networks Analysis and Mining. 555--556","author":"Conghuan Ye","year":"2011","unstructured":"Ye Conghuan. 2011. Dense Subgroup Identifying in Social Network. In International Conference on Advances in Social Networks Analysis and Mining. 555--556."},{"key":"e_1_2_2_14_1","volume-title":"IEEE High Performance Extreme Computing Conference (HPEC). 1--6.","author":"Conte Alessio","year":"2018","unstructured":"Alessio Conte, Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. 2018. Discovering k-Trusses in Large-Scale Networks. In IEEE High Performance Extreme Computing Conference (HPEC). 1--6."},{"key":"e_1_2_2_15_1","volume-title":"Introduction to Algorithms (3. ed.)","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3. ed.). MIT Press."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00077"},{"key":"e_1_2_2_18_1","volume-title":"Nucleus Decomposition in Probabilistic Graphs: Hardness and Algorithms. In IEEE International Conference on Data Engineering (ICDE). 218--231","author":"Esfahani Fatemeh","year":"2022","unstructured":"Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. 2022. Nucleus Decomposition in Probabilistic Graphs: Hardness and Algorithms. In IEEE International Conference on Data Engineering (ICDE). 218--231."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_2_20_1","volume-title":"Computing the Degeneracy of Large Graphs. In Latin American Symposium on Theoretical Informatics. 250--260","author":"Farach-Colton Martin","year":"2014","unstructured":"Martin Farach-Colton and Meng-Tsung Tsai. 2014. Computing the Degeneracy of Large Graphs. In Latin American Symposium on Theoretical Informatics. 250--260."},{"key":"e_1_2_2_21_1","first-page":"e150","article-title":"MotifCut","volume":"22","author":"Fratkin Eugene","year":"2006","unstructured":"Eugene Fratkin, Brian T Naughton, Douglas L Brutlag, and Serafim Batzoglou. 2006. MotifCut: Regulatory Motifs Finding with Maximum Density Subgraphs. Bioinformatics, Vol. 22, 14 (2006), e150--e157.","journal-title":"Regulatory Motifs Finding with Maximum Density Subgraphs. Bioinformatics"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220066"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning. 2201--2210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi\u0107. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In Proceedings of the 36th International Conference on Machine Learning. 2201--2210."},{"key":"e_1_2_2_24_1","volume-title":"Proc. VLDB Endow. 721--732","author":"Gibson David","year":"2005","unstructured":"David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In Proc. VLDB Endow. 721--732."},{"key":"e_1_2_2_25_1","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS). 698--710","author":"Gil J.","unstructured":"J. Gil, Y. Matias, and U. Vishkin. 1991. Towards a Theory of Nearly Constant Time Parallel Algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS). 698--710."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2960226"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_2_29_1","volume-title":"Efficient Algorithms for Parallel Bi-core Decomposition. In Symposium on Algorithmic Principles of Computer Systems (APOCS). 17--32","author":"Huang Yihao","year":"2023","unstructured":"Yihao Huang, Claire Wang, Jessica Shi, and Julian Shun. 2023. Efficient Algorithms for Parallel Bi-core Decomposition. In Symposium on Algorithmic Principles of Computer Systems (APOCS). 17--32."},{"key":"e_1_2_2_30_1","volume-title":"Introduction to Parallel Algorithms","author":"Jaja J.","unstructured":"J. Jaja. 1992. Introduction to Parallel Algorithms. Addison-Wesley Professional."},{"key":"e_1_2_2_31_1","volume-title":"ACM Symposium on Principles of Distributed Computing (PODC). 75--82","author":"Siddhartha","unstructured":"Siddhartha V. Jayanti and Robert E. Tarjan. 2016. A Randomized Concurrent Algorithm for Disjoint Set Union. In ACM Symposium on Principles of Distributed Computing (PODC). 75--82."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2835441"},{"key":"e_1_2_2_33_1","volume-title":"IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 1482--1491","author":"Kabir H.","unstructured":"H. Kabir and K. Madduri. 2017a. Parallel k-Core Decomposition on Multicore Platforms. In IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 1482--1491."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091052"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430929"},{"key":"e_1_2_2_37_1","unstructured":"Jure Leskovec and Andrej Krevl. 2019. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_2_40_1","first-page":"1075","article-title":"Efficient ((\u03b1), (\u03b2))-Core Computation in Bipartite Graphs","volume":"29","author":"Liu Boge","year":"2020","unstructured":"Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2020. Efficient ((\u03b1), (\u03b2))-Core Computation in Bipartite Graphs. Proc. VLDB Endow., Vol. 29, 5 (2020), 1075--1099.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547718"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2020.3026574"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Qi Luo Dongxiao Yu Hao Sheng Jiguo Yu and Xiuzhen Cheng. 2021. Distributed Algorithm for Truss Maintenance in Dynamic Graphs. In Parallel and Distributed Computing Applications and Technologies (PDCAT). 104--115.","DOI":"10.1007\/978-3-030-69244-5_9"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_2_47_1","volume-title":"Motif-Driven Dense Subgraph Discovery in Directed and Labeled Networks. In The Web Conference (WWW). 379--390","author":"Ahmet Erdem","year":"2021","unstructured":"Ahmet Erdem Sariy\u00fc ce. 2021. Motif-Driven Dense Subgraph Discovery in Directed and Labeled Networks. In The Web Conference (WWW). 379--390."},{"key":"e_1_2_2_48_1","first-page":"425","article-title":"Incremental k-Core Decomposition","volume":"25","author":"Sariy\u00fcce Ahmet Erdem","year":"2016","unstructured":"Ahmet Erdem Sariy\u00fcce, Buug ra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and \u00dcmit V cC ataly\u00fcrek. 2016. Incremental k-Core Decomposition: Algorithms and Evaluation. Proc. VLDB Endow., Vol. 25, 3 (2016), 425--447.","journal-title":"Algorithms and Evaluation. Proc. VLDB Endow."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_2_2_50_1","volume-title":"Peeling Bipartite Networks for Dense Subgraph Discovery. In ACM International Conference on Web Search and Data Mining (WSDM). 504--512","author":"Erdem Ahmet","unstructured":"Ahmet Erdem Sariy\u00fc ce and Ali Pinar. 2018. Peeling Bipartite Networks for Dense Subgraph Discovery. In ACM International Conference on Web Search and Data Mining (WSDM). 504--512."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3057742"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_2_54_1","volume-title":"Parallel Clique Counting and Peeling Algorithms. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA). 135--146","author":"Shi Jessica","year":"2021","unstructured":"Jessica Shi, Laxman Dhulipala, and Julian Shun. 2021. Parallel Clique Counting and Peeling Algorithms. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA). 135--146."},{"key":"e_1_2_2_55_1","first-page":"3","article-title":"Theoretically and Practically Efficient Parallel Nucleus Decomposition","volume":"15","author":"Shi Jessica","year":"2022","unstructured":"Jessica Shi, Laxman Dhulipala, and Julian Shun. 2022. Theoretically and Practically Efficient Parallel Nucleus Decomposition. Proc. VLDB Endow., Vol. 15, 3 (feb 2022), 583--596.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_2_56_1","unstructured":"Jessica Shi Laxman Dhulipala and Julian Shun. 2023. Parallel Algorithms for Hierarchical Nucleus Decomposition. arxiv: 2306.08623 [cs.DC]"},{"key":"e_1_2_2_57_1","volume-title":"Parallel Algorithms for Butterfly Computations. In SIAM Symposium on Algorithmic Principles of Computer Systems (APoCS). 16--30","author":"Shi Jessica","year":"2020","unstructured":"Jessica Shi and Julian Shun. 2020. Parallel Algorithms for Butterfly Computations. In SIAM Symposium on Algorithmic Principles of Computer Systems (APoCS). 16--30."},{"key":"e_1_2_2_58_1","volume-title":"Truss Decomposition on Shared-Memory Parallel Systems. In IEEE High Performance Extreme Computing Conference (HPEC). 1--6.","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith, Xing Liu, Nesreen K Ahmed, Ancy Sarah Tom, Fabrizio Petrini, and George Karypis. 2017. Truss Decomposition on Shared-Memory Parallel Systems. In IEEE High Performance Extreme Computing Conference (HPEC). 1--6."},{"key":"e_1_2_2_59_1","article-title":"Fully Dynamic Approximate k-Core Decomposition in Hypergraphs","volume":"14","author":"Sun Bintao","year":"2020","unstructured":"Bintao Sun, T.-H. Hubert Chan, and Mauro Sozio. 2020. Fully Dynamic Approximate k-Core Decomposition in Hypergraphs. ACM Trans. Knowl. Discov. Data (TKDD), Vol. 14, 4, Article 39 (May 2020).","journal-title":"ACM Trans. Knowl. Discov. Data (TKDD)"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_2_61_1","volume-title":"Finding Dense Subgraph for Community Detection on Social Network Based on Information Diffusion. In International Conference on Data and Software Engineering (ICoDSE). 1--6.","author":"Venica Liptia","year":"2021","unstructured":"Liptia Venica and Gusti Ayu Putri Saptawati. 2021. Finding Dense Subgraph for Community Detection on Social Network Based on Information Diffusion. In International Conference on Data and Software Engineering (ICoDSE). 1--6."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_2_63_1","volume-title":"Efficient Bitruss Decomposition for Large-Scale Bipartite Graphs. In IEEE International Conference on Data Engineering (ICDE). 661--672","author":"Wang Kai","year":"2020","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient Bitruss Decomposition for Large-Scale Bipartite Graphs. In IEEE International Conference on Data Engineering (ICDE). 661--672."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"},{"key":"e_1_2_2_66_1","volume-title":"Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs. In ACM SIGMOD International Conference on Management of Data. 1024--1041","author":"Zhang Yikai","year":"2019","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2019. Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs. In ACM SIGMOD International Conference on Management of Data. 1024--1041."},{"key":"e_1_2_2_67_1","volume-title":"IEEE International Conference on Data Engineering (ICDE). 337--348","author":"Zhang Y.","unstructured":"Y. Zhang, J. X. Yu, Y. Zhang, and L. Qin. 2017. A Fast Order-Based Approach for Core Maintenance. In IEEE International Conference on Data Engineering (ICDE). 337--348."},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_2_2_69_1","doi-asserted-by":"crossref","unstructured":"Zhaonian Zou. 2016. Bitruss Decomposition of Bipartite Graphs. In Database Systems for Advanced Applications (DASFAA). 218--233.","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639287","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:28Z","timestamp":1755789388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639287"],"URL":"https:\/\/doi.org\/10.1145\/3639287","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}