{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T15:48:03Z","timestamp":1786636083055,"version":"build-2736575974"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>\n            Given a directed graph\n            <jats:italic>G<\/jats:italic>\n            and integers\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>l<\/jats:italic>\n            , a D-core is the maximal subgraph\n            <jats:italic>H<\/jats:italic>\n            \u2286\n            <jats:italic>G<\/jats:italic>\n            such that for every vertex of\n            <jats:italic>H<\/jats:italic>\n            , its in-degree and out-degree are no smaller than\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>l<\/jats:italic>\n            , respectively. For a directed graph\n            <jats:italic>G<\/jats:italic>\n            , the problem of D-core decomposition aims to compute the non-empty D-cores for all possible values of\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>l.<\/jats:italic>\n            In the literature, several\n            <jats:italic>peeling-based<\/jats:italic>\n            algorithms have been proposed to handle D-core decomposition. However, the peeling-based algorithms that work in a sequential fashion and require global graph information during processing are mainly designed for\n            <jats:italic>centralized<\/jats:italic>\n            settings, which cannot handle large-scale graphs efficiently in distributed settings. Motivated by this, we study the\n            <jats:italic>distributed<\/jats:italic>\n            D-core decomposition problem in this paper. We start by defining a concept called\n            <jats:italic>anchored coreness<\/jats:italic>\n            , based on which we propose a new H-index-based algorithm for distributed D-core decomposition. Furthermore, we devise a novel concept, namely\n            <jats:italic>skyline coreness<\/jats:italic>\n            , and show that the D-core decomposition problem is equivalent to the computation of skyline corenesses for all vertices. We design an efficient D-index to compute the skyline corenesses distributedly. We implement the proposed algorithms under both vertex-centric and block-centric distributed graph processing frameworks. Moreover, we theoretically analyze the algorithm and message complexities. Extensive experiments on large real-world graphs with billions of edges demonstrate the efficiency of the proposed algorithms in terms of both the running time and communication overhead.\n          <\/jats:p>","DOI":"10.14778\/3529337.3529340","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:05Z","timestamp":1655936585000},"page":"1546-1558","source":"Crossref","is-referenced-by-count":31,"title":["Distributed D-core decomposition over large directed graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Xuankun","family":"Liao","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaxin","family":"Jiang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2012. Giraph. https:\/\/giraph.apache.org\/.  2012. Giraph. https:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Ganesh Ananthanarayanan Srikanth Kandula Albert G. Greenberg Ion Stoica Yi Lu Bikas Saha and Edward Harris. 2010. Reining in the Outliers in Map-Reduce Clusters using Mantri. In OSDI. 265--278.  Ganesh Ananthanarayanan Srikanth Kandula Albert G. Greenberg Ion Stoica Yi Lu Bikas Saha and Edward Harris. 2010. Reining in the Outliers in Map-Reduce Clusters using Mantri. In OSDI. 265--278."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933267.2933299"},{"key":"e_1_2_1_4_1","volume-title":"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 ). 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.1145\/2623330.2623655"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/490"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004366"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.062819"},{"key":"e_1_2_1_11_1","volume-title":"International Conference on Machine Learning. 1397--1406","author":"Esfandiari Hossein","year":"2018","unstructured":"Hossein Esfandiari , Silvio Lattanzi , and Vahab Mirrokni . 2018 . Parallel and streaming algorithms for k-core decomposition . In International Conference on Machine Learning. 1397--1406 . Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. 2018. Parallel and streaming algorithms for k-core decomposition. In International Conference on Machine Learning. 1397--1406."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137801"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418226"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/poi3.151"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0539-0"},{"key":"e_1_2_1_18_1","unstructured":"Jorge E. Hirsch. 2005. H-index. https:\/\/en.wikipedia.org\/wiki\/H-index\/.  Jorge E. Hirsch. 2005. H-index. https:\/\/en.wikipedia.org\/wiki\/H-index\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.211"},{"key":"e_1_2_1_20_1","volume-title":"Laks VS Lakshmanan, and Jianliang Xu","author":"Huang Xin","year":"2019","unstructured":"Xin Huang , Laks VS Lakshmanan, and Jianliang Xu . 2019 . Community Search over Big Graphs. Morgan & Claypool Publishers . Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2019. Community Search over Big Graphs. Morgan & Claypool Publishers."},{"key":"e_1_2_1_21_1","volume-title":"Metis: A software package for partitioning unstructured graphs. Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar . 1998 . Metis: A software package for partitioning unstructured graphs. Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4 (1998). George Karypis and Vipin Kumar. 1998. Metis: A software package for partitioning unstructured graphs. Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4 (1998)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Xunkun Liao Qing Liu Jiaxin Jiang Xin Huang Jianliang Xu and Byron Choi. 2022. Distributed D-core Decomposition over Large Directed Graphs. In arXivpreprint arXiv:2202.05990.  Xunkun Liao Qing Liu Jiaxin Jiang Xin Huang Jianliang Xu and Byron Choi. 2022. Distributed D-core Decomposition over Large Directed Graphs. In arXivpreprint arXiv:2202.05990.","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_25_1","volume-title":"International World Wide Web Conference. 1130--1141","author":"Liu Boge","year":"2019","unstructured":"Boge Liu , Long Yuan , Xuemin Lin , Lu Qin , Wenjie Zhang , and Jingren Zhou . 2019 . Efficient (&alpha;,\u03b2)-core Computation: an Index-based Approach . In International World Wide Web Conference. 1130--1141 . Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2019. Efficient (&alpha;,\u03b2)-core Computation: an Index-based Approach. In International World Wide Web Conference. 1130--1141."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_28_1","volume-title":"Distributed graphlab: A framework for machine learning in the cloud. arXiv preprint arXiv:1204.6078","author":"Low Yucheng","year":"2012","unstructured":"Yucheng Low , Joseph Gonzalez , Aapo Kyrola , Danny Bickson , Carlos Guestrin , and Joseph M Hellerstein . 2012. Distributed graphlab: A framework for machine learning in the cloud. arXiv preprint arXiv:1204.6078 ( 2012 ). Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M Hellerstein. 2012. Distributed graphlab: A framework for machine learning in the cloud. arXiv preprint arXiv:1204.6078 (2012)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10168"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258018"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_34_1","volume-title":"Efficient Probabilistic K-Core Computation on Uncertain Graphs. In IEEE International Conference on Data Engineering. 1192--1203","author":"Peng You","year":"2018","unstructured":"You Peng , Ying Zhang , Wenjie Zhang , Xuemin Lin , and Lu Qin . 2018 . Efficient Probabilistic K-Core Computation on Uncertain Graphs. In IEEE International Conference on Data Engineering. 1192--1203 . You Peng, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Lu Qin. 2018. Efficient Probabilistic K-Core Computation on Uncertain Graphs. In IEEE International Conference on Data Engineering. 1192--1203."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2017.00171"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-020-00857-0"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3529337.3529340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:44:07Z","timestamp":1672220647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3529337.3529340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":46,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.14778\/3529337.3529340"],"URL":"https:\/\/doi.org\/10.14778\/3529337.3529340","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}