{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:12:56Z","timestamp":1755839576912},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p>\n            The higher-order structure cohesive subgraph mining is an important operator in many graph analysis tasks. Recently, the colorful\n            <jats:italic>h<\/jats:italic>\n            -star core model has been proposed as an effective alternative to\n            <jats:italic>h<\/jats:italic>\n            -clique based cohesive subgraph models, in consideration of both efficiency and utilities in many practical applications. The existing peeling algorithms for colorful\n            <jats:italic>h<\/jats:italic>\n            -star core decomposition are to iteratively delete a node with the minimum colorful\n            <jats:italic>h<\/jats:italic>\n            -star degree. Hence, these methods are inherently sequential and suffer from two limitations: low parallelism and inefficiency for dynamic graphs. To enable high-performance colorful\n            <jats:italic>h<\/jats:italic>\n            -star core decomposition in large-scale graphs, we propose highly parallelizable local algorithms based on a novel concept of colorful\n            <jats:italic>h<\/jats:italic>\n            -star\n            <jats:italic>n<\/jats:italic>\n            -order H-index and conduct thorough analyses for its properties. Moreover, three optimizations have been developed to further improve the convergence performance. Based on our local algorithm and its optimized variants, we can efficiently maintain colorful\n            <jats:italic>h<\/jats:italic>\n            -star cores in dynamic graphs. Furthermore, we design lower and upper bounds for core numbers to facilitate identifying unaffected nodes in presence of graph updates. Extensive experiments conducted on 14 large real-world datasets with billions of edges demonstrate that our proposed algorithms achieve a 10 times faster convergence speed and a three orders of magnitude speedup when handling graph changes.\n          <\/jats:p>","DOI":"10.14778\/3603581.3603593","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:06:48Z","timestamp":1691521608000},"page":"2538-2550","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Parallel Colorful\n            <i>h<\/i>\n            -Star Core Maintenance in Dynamic Graphs"],"prefix":"10.14778","volume":"16","author":[{"given":"Sen","family":"Gao","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"41","volume-title":"NIPS","author":"Alvarez-Hamelin J. I.","year":"2005","unstructured":"J. I. Alvarez-Hamelin , L. Dall'Asta , A. Barrat , and A. Vespignani . Large scale networks fingerprinting and visualization using the k-core decomposition . In NIPS , pages 41 -- 50 , 2005 . J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In NIPS, pages 41--50, 2005."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3934\/nhm.2008.3.371"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-021-00805-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30165-5_30"},{"key":"e_1_2_1_5_1","volume-title":"An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik . An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049 , 2003 . V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049, 2003."},{"key":"e_1_2_1_6_1","volume-title":"Higher-order organization of complex networks. Science, 353(6295)","author":"Benson A. R.","year":"2016","unstructured":"A. R. Benson , D. F. Gleich , and J. Leskovec . Higher-order organization of complex networks. Science, 353(6295) , 2016 . A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353(6295), 2016."},{"key":"e_1_2_1_7_1","volume-title":"KDD","author":"Bonchi F.","year":"2014","unstructured":"F. Bonchi , F. Gullo , A. Kaltenbrunner , and Y. Volkovich . Core decomposition of uncertain graphs . In KDD , 2014 . F. Bonchi, F. Gullo, A. Kaltenbrunner, and Y. Volkovich. Core decomposition of uncertain graphs. In KDD, 2014."},{"key":"e_1_2_1_8_1","volume-title":"SIGMOD","author":"Bonchi F.","year":"2019","unstructured":"F. Bonchi , A. Khan , and L. Severini . Distance-generalized core decomposition. In P. A. Boncz, S. Manegold, A. Ailamaki, A. Deshpande, and T. Kraska, editors , SIGMOD , 2019 . F. Bonchi, A. Khan, and L. Severini. Distance-generalized core decomposition. In P. A. Boncz, S. Manegold, A. Ailamaki, A. Deshpande, and T. Kraska, editors, SIGMOD, 2019."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_12_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. Technical report","author":"Cohen J.","year":"2005","unstructured":"J. Cohen . Trusses: Cohesive subgraphs for social network analysis. Technical report , National Security Agency , 2005 . J. Cohen. Trusses: Cohesive subgraphs for social network analysis. Technical report, National Security Agency, 2005."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137801"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_15_1","first-page":"2588","volume-title":"ICDE","author":"Gao S.","year":"2022","unstructured":"S. Gao , R. Li , H. Qin , H. Chen , Y. Yuan , and G. Wang . Colorful h-star core decomposition . In ICDE , pages 2588 -- 2601 . IEEE, 2022 . S. Gao, R. Li, H. Qin, H. Chen, Y. Yuan, and G. Wang. Colorful h-star core decomposition. In ICDE, pages 2588--2601. IEEE, 2022."},{"key":"e_1_2_1_16_1","volume-title":"Parallel colorful h-star core maintenance in dynamic graphs","author":"Gao S.","year":"2023","unstructured":"S. Gao , H. Qin , R.-H. Li , and B. He . Parallel colorful h-star core maintenance in dynamic graphs . 2023 . available at: https:\/\/github.com\/Gawssin\/ColorfulStarLocal\/blob\/main\/FullVersion.pdf. S. Gao, H. Qin, R.-H. Li, and B. He. Parallel colorful h-star core maintenance in dynamic graphs. 2023. available at: https:\/\/github.com\/Gawssin\/ColorfulStarLocal\/blob\/main\/FullVersion.pdf."},{"key":"e_1_2_1_17_1","volume-title":"SPAA","author":"Hasenplaugh W.","year":"2014","unstructured":"W. Hasenplaugh , T. Kaler , T. B. Schardl , and C. E. Leiserson . Ordering heuristics for parallel graph coloring . In SPAA , 2014 . W. Hasenplaugh, T. Kaler, T. B. Schardl, and C. E. Leiserson. Ordering heuristics for parallel graph coloring. In SPAA, 2014."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2960226"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_20_1","volume-title":"ICDE","author":"Huang X.","year":"2017","unstructured":"X. Huang , L. V. Lakshmanan , and J. Xu . Community search over big graphs: Models, algorithms, and opportunities . In ICDE , 2017 . X. Huang, L. V. Lakshmanan, and J. Xu. Community search over big graphs: Models, algorithms, and opportunities. In ICDE, 2017."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-4-2","article-title":"An automated method for finding molecular complexes in large protein interaction networks","volume":"4","author":"Kitsak M.","year":"2003","unstructured":"M. Kitsak , L. K. Gallos , S. Havlin , F. Liljeros , L. Muchnik , H. E. Stanley , and H. A. Makse . An automated method for finding molecular complexes in large protein interaction networks . BMC Bioinformatics , 4 : 2 , 2003 . M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4:2, 2003.","journal-title":"BMC Bioinformatics"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10168"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_30_1","volume-title":"SIAM Workshop on Network Science, 01","author":"Rossi R.","year":"2013","unstructured":"R. Rossi , D. Gleich , and A. Gebremedhin . Triangle core decomposition and maximum cliques . SIAM Workshop on Network Science, 01 2013 . R. Rossi, D. Gleich, and A. Gebremedhin. Triangle core decomposition and maximum cliques. SIAM Workshop on Network Science, 01 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"R. A.\n      Rossi\n    . \n      Fast\n     triangle core decomposition for mining large graphs.\n   volume \n  8443\n   of \n  Lecture Notes in Computer Science pages \n  310\n  --\n  322\n  . \n  Springer 2014\n  .  R. A. Rossi. Fast triangle core decomposition for mining large graphs. volume 8443 of Lecture Notes in Computer Science pages 310--322. Springer 2014.","DOI":"10.1007\/978-3-319-06608-0_26"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_33_1","volume-title":"A graph-theoretic algorithm for comparative modeling of protein structure. Journal of molecular biology, 279(1):287--302","author":"Samudrala R.","year":"1998","unstructured":"R. Samudrala and J. Moult . A graph-theoretic algorithm for comparative modeling of protein structure. Journal of molecular biology, 279(1):287--302 , 1998 . R. Samudrala and J. Moult. A graph-theoretic algorithm for comparative modeling of protein structure. Journal of molecular biology, 279(1):287--302, 1998."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3057742"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01898.x"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_1_45_1","first-page":"5","article-title":"Peeling the yeast protein network","author":"Wuchty S.","year":"2005","unstructured":"S. Wuchty and E. Almaas . Peeling the yeast protein network . Proteomics , 5 , 2005 . S. Wuchty and E. Almaas. Peeling the yeast protein network. Proteomics, 5, 2005.","journal-title":"Proteomics"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2021.3064836"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157802"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3603581.3603593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:09:41Z","timestamp":1691521781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3603581.3603593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":49,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.14778\/3603581.3603593"],"URL":"https:\/\/doi.org\/10.14778\/3603581.3603593","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"2023-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}