{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:36:21Z","timestamp":1778279781844,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:p>\n            The distance-generalized core, also called (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core, is defined as the maximal subgraph in which every vertex has at least\n            <jats:italic>k<\/jats:italic>\n            vertices at distance no longer than\n            <jats:italic>h.<\/jats:italic>\n            Compared with\n            <jats:italic>k<\/jats:italic>\n            -core, (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core can identify more fine-grained subgraphs and, hence, is more useful for the applications such as network analysis and graph coloring. The state-of-the-art algorithms for (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core decomposition are peeling algorithms, which iteratively delete the vertex with the minimum\n            <jats:italic>h<\/jats:italic>\n            -degree (i.e., the least number of neighbors within\n            <jats:italic>h<\/jats:italic>\n            hops). However, they suffer from some limitations, such as low parallelism and incapability of supporting dynamic graphs. To address these limitations, in this paper, we revisit the problem of (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core decomposition. First, we introduce two novel concepts of\n            <jats:italic>pairwise h-attainability index<\/jats:italic>\n            and\n            <jats:italic>n-order H-index<\/jats:italic>\n            based on an insightful observation. Then, we thoroughly analyze the properties of\n            <jats:italic>n<\/jats:italic>\n            -order H-index and propose a parallelizable local algorithm for (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core decomposition. Moreover, several optimizations are presented to accelerate the local algorithm. Furthermore, we extend the proposed local algorithm to address the (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core maintenance problem for dynamic graphs. Experimental studies on real-world graphs show that, compared to the best existing solution, our proposed algorithms can reduce the (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>h<\/jats:italic>\n            )-core decomposition time by 1--3 orders of magnitude and save the maintenance cost by 1--2 orders of magnitude.\n          <\/jats:p>","DOI":"10.14778\/3461535.3461542","type":"journal-article","created":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T22:22:49Z","timestamp":1634941369000},"page":"1531-1543","source":"Crossref","is-referenced-by-count":24,"title":["Local algorithms for distance-generalized core decomposition over large dynamic graphs"],"prefix":"10.14778","volume":"14","author":[{"given":"Qing","family":"Liu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuliang","family":"Zhu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297918"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2976248.2976254"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3934\/nhm.2008.3.371"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.11.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Vladimir Batagelj Andrej Mrvar and Matjaz Zaversnik. 1999. Partitioning Approach to Visualization of Large Graphs. In GD. 90--97.  Vladimir Batagelj Andrej Mrvar and Matjaz Zaversnik. 1999. Partitioning Approach to Visualization of Large Graphs. In GD. 90--97.","DOI":"10.1007\/3-540-46648-7_9"},{"key":"e_1_2_1_6_1","volume-title":"CoRR cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339724"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_15_1","unstructured":"Naga Shailaja Dasari Desh Ranjan and Mohammad Zubair. 2014. ParK: An efficient algorithm for k-core decomposition on multicore processors. In Big Data. 9--16.  Naga Shailaja Dasari Desh Ranjan and Mohammad Zubair. 2014. ParK: An efficient algorithm for k-core decomposition on multicore processors. In Big Data. 9--16."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.062819"},{"key":"e_1_2_1_17_1","volume-title":"Mirrokni","author":"Esfandiari Hossein","year":"2018"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418226"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.46"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0507655102"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2960226"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3365087"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882913"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2835441"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_32_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"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258018"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592052"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.136"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"You Peng Ying Zhang Wenjie Zhang Xuemin Lin and Lu Qin. 2018. Efficient Probabilistic K-Core Computation on Uncertain Graphs. In ICDE. 1192--1203.  You Peng Ying Zhang Wenjie Zhang Xuemin Lin and Lu Qin. 2018. Efficient Probabilistic K-Core Computation on Uncertain Graphs. In ICDE. 1192--1203.","DOI":"10.1109\/ICDE.2018.00110"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01898.x"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Na Wang Dongxiao Yu Hai Jin Chen Qian Xia Xie and Qiang-Sheng Hua. 2017. Parallel Algorithm for Core Maintenance in Dynamic Graphs. In ICDCS. 2366--2371.  Na Wang Dongxiao Yu Hai Jin Chen Qian Xia Xie and Qiang-Sheng Hua. 2017. Parallel Algorithm for Core Maintenance in Dynamic Graphs. In ICDCS. 2366--2371.","DOI":"10.1109\/ICDCS.2017.288"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Dong Wen Lu Qin Ying Zhang Xuemin Lin and Jeffrey Xu Yu. 2016. I\/O efficient Core Graph Decomposition at web scale. In ICDE. 133--144.  Dong Wen Lu Qin Ying Zhang Xuemin Lin and Jeffrey Xu Yu. 2016. I\/O efficient Core Graph Decomposition at web scale. In ICDE. 133--144.","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-009-0299-0"},{"key":"e_1_2_1_51_1","volume-title":"Ying Zhang, and Lu Qin.","author":"Zhang Yikai","year":"2017"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Yi Zhou Jingwei Xu Zhenyu Guo Mingyu Xiao and Yan Jin. 2020. Enumerating Maximal k-Plexes with Worst-Case Time Guarantee. In AAAI. 2442--2449.  Yi Zhou Jingwei Xu Zhenyu Guo Mingyu Xiao and Yan Jin. 2020. Enumerating Maximal k -Plexes with Worst-Case Time Guarantee. In AAAI. 2442--2449.","DOI":"10.1609\/aaai.v34i03.5625"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3461535.3461542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:47:01Z","timestamp":1672220821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3461535.3461542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5]]},"references-count":52,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.14778\/3461535.3461542"],"URL":"https:\/\/doi.org\/10.14778\/3461535.3461542","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,5]]}}}