{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:36:41Z","timestamp":1791916601000,"version":"4.3.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>\n                    We propose\n                    <jats:italic>neighborhood-based core decomposition<\/jats:italic>\n                    : a novel way of decomposing hypergraphs into hierarchical neighborhood-cohesive subhypergraphs. Alternative approaches to decomposing hypergraphs, e.g., reduction to clique or bipartite graphs, are not meaningful in certain applications, the later also results in inefficient decomposition; while existing degree-based hypergraph decomposition does not distinguish nodes with different neighborhood sizes. Our case studies show that the proposed decomposition is more effective than degree and clique graph-based decompositions in disease intervention and in extracting provably approximate and application-wise meaningful densest subhypergraphs. We propose three algorithms: Peel, its efficient variant\n                    <jats:bold>E-Peel,<\/jats:bold>\n                    and a novel local algorithm:\n                    <jats:bold>Local-core<\/jats:bold>\n                    with parallel implementation. Our most efficient parallel algorithm\n                    <jats:bold>Local-core(P)<\/jats:bold>\n                    decomposes hypergraph with 27M nodes and 17M hyperedges in-memory within 91 seconds by adopting various optimizations. Finally, we develop a new hypergraph-core model, the\n                    <jats:italic>(neighborhood, degree)-core<\/jats:italic>\n                    by considering both neighborhood and degree constraints, design its decomposition algorithm\n                    <jats:bold>Local-core+Peel,<\/jats:bold>\n                    and demonstrate its superiority in spreading diffusion.\n                  <\/jats:p>","DOI":"10.14778\/3598581.3598582","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T18:19:06Z","timestamp":1689013146000},"page":"2061-2074","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Neighborhood-Based Hypergraph Core Decomposition"],"prefix":"10.14778","volume":"16","author":[{"given":"Naheed Anjum","family":"Arafat","sequence":"first","affiliation":[{"name":"NUS, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arijit","family":"Khan","sequence":"additional","affiliation":[{"name":"AAU, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arpit Kumar","family":"Rai","sequence":"additional","affiliation":[{"name":"IIT Kanpur, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bishwamittra","family":"Ghosh","sequence":"additional","affiliation":[{"name":"NUS, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Advances in Neural Information Processing Systems (NeurIPS)","author":"Alvarez-Hamelin J. Ignacio","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 Advances in Neural Information Processing Systems (NeurIPS) . MIT Press , 41--50. 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 Advances in Neural Information Processing Systems (NeurIPS). MIT Press, 41--50."},{"key":"e_1_2_1_2_1","volume-title":"Database and Expert Systems Applications (DEXA) (Lecture Notes in Computer Science)","author":"Arafat Naheed Anjum","unstructured":"Naheed Anjum Arafat , Debabrota Basu , Laurent Decreusefond , and St\u00e9phane Bressan . 2020. Construction and random generation of hypergraphs with prescribed degree and dimension sequences . In Database and Expert Systems Applications (DEXA) (Lecture Notes in Computer Science) , Vol. 12392 . Springer , 130--145. Naheed Anjum Arafat, Debabrota Basu, Laurent Decreusefond, and St\u00e9phane Bressan. 2020. Construction and random generation of hypergraphs with prescribed degree and dimension sequences. In Database and Expert Systems Applications (DEXA) (Lecture Notes in Computer Science), Vol. 12392. Springer, 130--145."},{"key":"e_1_2_1_3_1","volume-title":"Arpit Kumar Rai, and Bishwamittra Ghosh","author":"Arafat Naheed Anjum","year":"2022","unstructured":"Naheed Anjum Arafat , Arijit Khan , Arpit Kumar Rai, and Bishwamittra Ghosh . 2022 . Our code and datasets. https:\/\/github.com\/toggled\/vldbsubmission\/. Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and Bishwamittra Ghosh. 2022. Our code and datasets. https:\/\/github.com\/toggled\/vldbsubmission\/."},{"key":"e_1_2_1_4_1","volume-title":"Arpit Kumar Rai, and Bishwamittra Ghosh","author":"Arafat Naheed Anjum","year":"2023","unstructured":"Naheed Anjum Arafat , Arijit Khan , Arpit Kumar Rai, and Bishwamittra Ghosh . 2023 . Neighborhood-based Hypergraph Core Decomposition . arXiv preprint arXiv:2301.06426 (2023). Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and Bishwamittra Ghosh. 2023. Neighborhood-based Hypergraph Core Decomposition. arXiv preprint arXiv:2301.06426 (2023)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341161.3342867"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.20429\/tag.2015.020205"},{"key":"e_1_2_1_7_1","unstructured":"Stephen Bailey. 2017. Nashville meetup network. https:\/\/www.kaggle.com\/datasets\/stkbailey\/nashville-meetup.  Stephen Bailey. 2017. Nashville meetup network. https:\/\/www.kaggle.com\/datasets\/stkbailey\/nashville-meetup."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11634-010-0079-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2020.05.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_1_12_1","volume-title":"Hypergraphs - combinatorics of finite sets. North-Holland mathematical library","author":"Berge Claude","unstructured":"Claude Berge . 1989. Hypergraphs - combinatorics of finite sets. North-Holland mathematical library , Vol. 45 . North-Holland . Claude Berge. 1989. Hypergraphs - combinatorics of finite sets. North-Holland mathematical library, Vol. 45. North-Holland."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_14_1","volume-title":"Third International Workshop (Lecture Notes in Computer Science)","volume":"1913","author":"Charikar Moses","year":"2000","unstructured":"Moses Charikar . 2000 . Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization , Third International Workshop (Lecture Notes in Computer Science) , Vol. 1913 . Springer, 84--95. Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, Third International Workshop (Lecture Notes in Computer Science), Vol. 1913. Springer, 84--95."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_16_1","volume-title":"Subhypergraphs in non-uniform random hypergraphs. Internet Math. 2018","author":"Dewar Megan","year":"2018","unstructured":"Megan Dewar , Kirill Ternovsky , Benjamin Reiniger , John Proos , Pawel Pralat , Xavier P\u00e9rez-Gim\u00e9nez , and John Healy . 2018. Subhypergraphs in non-uniform random hypergraphs. Internet Math. 2018 ( 2018 ). Megan Dewar, Kirill Ternovsky, Benjamin Reiniger, John Proos, Pawel Pralat, Xavier P\u00e9rez-Gim\u00e9nez, and John Healy. 2018. Subhypergraphs in non-uniform random hypergraphs. Internet Math. 2018 (2018)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1513876.1513879"},{"key":"e_1_2_1_18_1","first-page":"139","article-title":"Higher-order graph models: from theoretical foundations to machine learning (Dagstuhl Seminar 21352)","volume":"11","author":"Eliassi-Rad Tina","year":"2021","unstructured":"Tina Eliassi-Rad , Vito Latora , Martin Rosvall , and Ingo Scholtes . 2021 . Higher-order graph models: from theoretical foundations to machine learning (Dagstuhl Seminar 21352) . Dagstuhl Reports 11 , 7 (2021), 139 -- 178 . Tina Eliassi-Rad, Vito Latora, Martin Rosvall, and Ingo Scholtes. 2021. Higher-order graph models: from theoretical foundations to machine learning (Dagstuhl Seminar 21352). Dagstuhl Reports 11, 7 (2021), 139--178.","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556565"},{"key":"e_1_2_1_21_1","unstructured":"Andrew Finlayson. [n.d.]. OpenMP Scheduling. http:\/\/www.inf.ufsc.br\/~bosco.sobral\/ensino\/ine5645\/OpenMP_Dynamic_Scheduling.pdf.  Andrew Finlayson. [n.d.]. OpenMP Scheduling. http:\/\/www.inf.ufsc.br\/~bosco.sobral\/ensino\/ine5645\/OpenMP_Dynamic_Scheduling.pdf."},{"key":"e_1_2_1_22_1","volume-title":"Stadler","author":"Flamm Christoph","year":"2015","unstructured":"Christoph Flamm , B\u00e4rbel M.R. Stadler , and Peter F . Stadler . 2015 . Generalized topologies: hypergraphs, chemical reactions, and biological evolution. In Advances in Mathematical Chemistry and Applications. Bentham Science , 300--328. Christoph Flamm, B\u00e4rbel M.R. Stadler, and Peter F. Stadler. 2015. Generalized topologies: hypergraphs, chemical reactions, and biological evolution. In Advances in Mathematical Chemistry and Applications. Bentham Science, 300--328."},{"key":"e_1_2_1_23_1","volume-title":"IEEE International Parallel and Distributed Processing Symposium. 998--1007","author":"Gabert Kasimir","year":"2021","unstructured":"Kasimir Gabert , Ali Pinar , and \u00dcmit V. \u00c7ataly\u00fcrek . 2021 . Shared-Memory Scalable k-Core Maintenance on Dynamic Graphs and Hypergraphs . In IEEE International Parallel and Distributed Processing Symposium. 998--1007 . Kasimir Gabert, Ali Pinar, and \u00dcmit V. \u00c7ataly\u00fcrek. 2021. Shared-Memory Scalable k-Core Maintenance on Dynamic Graphs and Hypergraphs. In IEEE International Parallel and Distributed Processing Symposium. 998--1007."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty570"},{"key":"e_1_2_1_26_1","volume-title":"Finding a maximum density subgraph","author":"Goldberg Andrew V.","unstructured":"Andrew V. Goldberg . 1984. Finding a maximum density subgraph . University of California Berkeley . Andrew V. Goldberg. 1984. Finding a maximum density subgraph. University of California Berkeley."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_28_1","unstructured":"Ronald L. Graham Martin Gr\u00f6tschel and L\u00e1szl\u00f3 Lov\u00e1sz (Eds.). 1996. Handbook of Combinatorics (Vol. 2). MIT Press.  Ronald L. Graham Martin Gr\u00f6tschel and L\u00e1szl\u00f3 Lov\u00e1sz (Eds.). 1996. Handbook of Combinatorics (Vol. 2). MIT Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.95"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0507655102"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.33"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2938412"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137650"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_36_1","volume-title":"Makse","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. 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_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3523275"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407823"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557505"},{"key":"e_1_2_1_40_1","volume-title":"Innovations in Theoretical Computer Science Conference (ITCS) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"94","author":"Legenstein Robert","unstructured":"Robert Legenstein , Wolfgang Maass , Christos H. Papadimitriou , and Santosh S. Vempala . 2018. Long term memory and the densest k-subgraph problem . In Innovations in Theoretical Computer Science Conference (ITCS) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 94 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 57:1--57:15. Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala. 2018. Long term memory and the densest k-subgraph problem. In Innovations in Theoretical Computer Science Conference (ITCS) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 94. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 57:1--57:15."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_42_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 ), 1--7. 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), 1--7."},{"key":"e_1_2_1_43_1","volume-title":"Locating influential nodes in complex networks. Scientific Reports 6","author":"Malliaros Fragkiskos D.","year":"1930","unstructured":"Fragkiskos D. Malliaros , Maria-Evgenia G. Rossi , and Michalis Vazirgiannis . 2016. Locating influential nodes in complex networks. Scientific Reports 6 , 1930 7 (2016). Fragkiskos D. Malliaros, Maria-Evgenia G. Rossi, and Michalis Vazirgiannis. 2016. Locating influential nodes in complex networks. Scientific Reports 6, 19307 (2016)."},{"key":"e_1_2_1_44_1","volume-title":"Interplay between k-core and community structure in complex networks. Scientific Reports 10, 14702","author":"Malvestio Irene","year":"2020","unstructured":"Irene Malvestio , Alessio Cardillo , and Naoki Masuda . 2020. Interplay between k-core and community structure in complex networks. Scientific Reports 10, 14702 ( 2020 ). Irene Malvestio, Alessio Cardillo, and Naoki Masuda. 2020. Interplay between k-core and community structure in complex networks. Scientific Reports 10, 14702 (2020)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2004.1303205"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374527"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385416"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3017120"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1355896"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377378"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i5.16578"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T19:01:39Z","timestamp":1689793299000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":57,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598582"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598582","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}