{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:36Z","timestamp":1779174876865,"version":"3.51.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62302417"],"award-info":[{"award-number":["62302417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    Hypergraphs provide a versatile framework for modeling complex relationships beyond pairwise interactions, finding applications in various domains.\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core decomposition is a fundamental task in hypergraph analysis that decomposes hypergraphs into cohesive substructures. Existing studies capture the cohesion in hypergraphs based on the vertex neighborhood size. However, such decomposition poses unique challenges, including the efficiency of core value updates, redundant computation, and high memory consumption. We observe that the state-of-the-art algorithms do not fully address the above challenges and are unable to scale to large hypergraphs. In this paper, we propose an efficient approach for hypergraph\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core decomposition. Novel concepts and strategies are developed to compute the core value of each vertex and reduce redundant computation of vertices. Experimental results on real-world and synthetic hypergraphs demonstrate that our approach significantly outperforms the state-of-the-art algorithm by 7 times on average while reducing the average memory usage by 36 times. Moreover, while existing algorithms fail on tens of millions hyperedges, our approach efficiently handles billion-scale hypergraphs in only a single thread.\n                  <\/jats:p>","DOI":"10.1145\/3709656","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":6,"title":["Accelerating Core Decomposition in Billion-Scale Hypergraphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-9999-9084","authenticated-orcid":false,"given":"Wenqian","family":"Zhang","sequence":"first","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1772-6863","authenticated-orcid":false,"given":"Zhengyi","family":"Yang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0903-1503","authenticated-orcid":false,"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4941-8814","authenticated-orcid":false,"given":"Wentao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Leicester, Leicester, United Kingdom, &amp; The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Edwin Norman Nilson, and Joseph LeonardWalsh","author":"Ahlberg J Harold","year":"2016","unstructured":"J Harold Ahlberg, Edwin Norman Nilson, and Joseph LeonardWalsh. 2016. The Theory of Splines and Their Applications: Mathematics in Science and Engineering: A Series of Monographs and Textbooks, Vol. 38. Vol. 38. Elsevier."},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 18th International Conference on Neural Information Processing Systems","author":"Alvarez-Hamelin J. Ignacio","year":"2005","unstructured":"J. Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Proceedings of the 18th International Conference on Neural Information Processing Systems (Vancouver, British Columbia, Canada) (NIPS'05). MIT Press, Cambridge, MA, USA, 41--50."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598582"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.20429\/tag.2015.020205"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.066102"},{"key":"e_1_2_2_6_1","unstructured":"C. Berge. 1973. Graphs and Hypergraphs. North-Holland Publishing Company. https:\/\/books.google.com.au\/books?id=X32GlVfqXjsC"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.109.014307"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-023-00956-2"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2011.09.017"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_2_12_1","volume-title":"Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018","volume":"879","author":"Chien I","year":"2018","unstructured":"I (Eli) Chien, Chung-Yi Lin, and I-Hsiang Wang. 2018. Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9--11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain (Proceedings of Machine Learning Research, Vol. 84), Amos J. Storkey and Fernando P\u00e9rez-Cruz (Eds.). PMLR, 871--879. http:\/\/proceedings.mlr.press\/v84\/chien18a.html"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096402"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004366"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_2_2_17_1","volume-title":"Complex networks as hypergraphs. arXiv preprint physics\/0505137","author":"Estrada Ernesto","year":"2005","unstructured":"Ernesto Estrada and Juan A Rodriguez-Velazquez. 2005. Complex networks as hypergraphs. arXiv preprint physics\/0505137 (2005)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/VIS49827.2021.9623305"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2011.65"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0507655102"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--56027--9_14"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2023.1301994"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.151"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583780.3615275"},{"key":"e_1_2_2_28_1","volume-title":"Identification of influential spreaders in complex networks. Nature physics 6, 11","author":"Kitsak Maksim","year":"2010","unstructured":"Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hern\u00e1n A Makse. 2010. Identification of influential spreaders in complex networks. Nature physics 6, 11 (2010), 888--893."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000385"},{"key":"e_1_2_2_30_1","volume-title":"A hypergraph-based method for large-scale dynamic correlation study at the transcriptomic scale. BMC genomics 20, 1","author":"Kong Yunchuan","year":"2019","unstructured":"Yunchuan Kong and Tianwei Yu. 2019. A hypergraph-based method for large-scale dynamic correlation study at the transcriptomic scale. BMC genomics 20, 1 (2019), 1--16."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450010"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.chaos.2023.113645"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219829"},{"key":"e_1_2_2_35_1","volume-title":"The H-index of a network node and its relation to degree and coreness. Nature communications 7, 1","author":"L\u00fc Linyuan","year":"2016","unstructured":"Linyuan L\u00fc, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016. The H-index of a network node and its relation to degree and coreness. Nature communications 7, 1 (2016), 10168."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00199"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00039"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627673.3679765"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2018.07.029"},{"key":"e_1_2_2_40_1","volume-title":"Specificity and stability in topology of protein networks. Science 296, 5569","author":"Maslov Sergei","year":"2002","unstructured":"Sergei Maslov and Kim Sneppen. 2002. Specificity and stability in topology of protein networks. Science 296, 5569 (2002), 910--913."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3655693.3661300"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbaa257"},{"key":"e_1_2_2_44_1","volume-title":"Jean-Marie Le Goff, and St\u00e9phane Marchand-Maillet","author":"Ouvrard Xavier","year":"2017","unstructured":"Xavier Ouvrard, Jean-Marie Le Goff, and St\u00e9phane Marchand-Maillet. 2017. Networks of collaborations: Hypergraph modeling and visualisation. arXiv preprint arXiv:1707.00115 (2017)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2004.1303205"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--91196-0_5"},{"key":"e_1_2_2_49_1","volume-title":"Network structure and minimum degree. Social networks 5, 3","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269--287."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385416"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2022.3168879"},{"key":"e_1_2_2_52_1","first-page":"6","article-title":"High-Order Local Clustering on Hypergraphs","volume":"11","author":"Wei Jingtian","year":"2024","unstructured":"Jingtian Wei, Zhengyi Yang, Qi Luo, Yu Zhang, Lu Qin, and Wenjie Zhang. 2024. High-Order Local Clustering on Hypergraphs. EAI Endorsed Transactions on Scalable Information Systems 11, 6 (Nov. 2024). https:\/\/doi.org\/10.4108\/ eetsis.7431","journal-title":"EAI Endorsed Transactions on Scalable Information Systems"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3023925"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00015"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00160"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.3390\/math10111921"},{"key":"e_1_2_2_60_1","volume-title":"Efficient Distributed Core Graph Decomposition. In 2023 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 1023--1031","author":"Zhang Wenqian","year":"2023","unstructured":"Wenqian Zhang, Zhengyi Yang, DongWen, and XiaoyangWang. 2023. Efficient Distributed Core Graph Decomposition. In 2023 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 1023--1031."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:16:04Z","timestamp":1774980964000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709656"],"URL":"https:\/\/doi.org\/10.1145\/3709656","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}