{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T16:00:58Z","timestamp":1774454458323,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>\n            Core maximization, that enlarges the\n            <jats:italic>k<\/jats:italic>\n            -core as much as possible by inserting a few new edges into a graph, is particularly useful for social group engagement and network stability improvement. However, the core maximization problem has been theoretically proven to be NP-hard even APX-hard for\n            <jats:italic>k<\/jats:italic>\n            \u2265 3. Existing heuristic approaches suffer from the limitation of inefficiency on large graphs. To address this limitation, in this paper, we revisit this challenging yet important problem of core maximization, that is, given a graph\n            <jats:italic>G<\/jats:italic>\n            , a number\n            <jats:italic>k<\/jats:italic>\n            , and a budget\n            <jats:italic>b<\/jats:italic>\n            , to insert\n            <jats:italic>b<\/jats:italic>\n            new edges into\n            <jats:italic>G<\/jats:italic>\n            such that the corresponding\n            <jats:italic>k<\/jats:italic>\n            -core is maximized. We propose a novel algorithm FastCM+ based on several fast search strategies. The core idea is to apply graph partition to divide (\n            <jats:italic>k<\/jats:italic>\n            - 1)-shell into different components. Then, FastCM+ considers each (\n            <jats:italic>k<\/jats:italic>\n            - 1)-shell component independently to convert different layered vertices into\n            <jats:italic>k<\/jats:italic>\n            -core, in two manners of completely and partially. Based on the complete\/partial conversions, FastCM+ is generalized to further handle (\n            <jats:italic>k<\/jats:italic>\n            - \u03bb)-shell conversions for 2 \u2264\u03bb\n            <jats:italic>k<\/jats:italic>\n            . Leveraging dynamic programming combinations of different components' potential answers, FastCM+ finds a good-quality answer for edge insertions. Experimental results on eleven datasets demonstrate that our algorithm runs much faster than state-of-the-art methods on large graphs meanwhile achieving better answers.\n          <\/jats:p>","DOI":"10.14778\/3523210.3523214","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:21Z","timestamp":1655936601000},"page":"1350-1362","source":"Crossref","is-referenced-by-count":16,"title":["Fast algorithms for core maximization on large graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Xin","family":"Sun","sequence":"first","affiliation":[{"name":"Computing, Tianjin University, Tianjin, China"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"given":"Di","family":"Jin","sequence":"additional","affiliation":[{"name":"Computing, Tianjin University, Tianjin, China"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"J Ignacio Alvarez-Hamelin Luca Dall'Asta Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In NeurIPS. 41--50.  J Ignacio Alvarez-Hamelin Luca Dall'Asta Alain Barrat and Alessandro Vespignani. 2006. Large scale networks fingerprinting and visualization using the k-core decomposition. In NeurIPS. 41--50."},{"key":"e_1_2_1_2_1","first-page":"443","article-title":"Edge Modification Criteria for Enhancing the Communicability of Digraphs","volume":"37","author":"Arrigo Francesca","year":"2016","unstructured":"Francesca Arrigo and Michele Benzi . 2016 . Edge Modification Criteria for Enhancing the Communicability of Digraphs . Siam Journal 37 , 1 (2016), 443 -- 468 . Francesca Arrigo and Michele Benzi. 2016. Edge Modification Criteria for Enhancing the Communicability of Digraphs. Siam Journal 37, 1 (2016), 443--468.","journal-title":"Siam Journal"},{"key":"e_1_2_1_3_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_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3166071"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/14097032X"},{"key":"e_1_2_1_6_1","volume-title":"Airline network development in Europe and its implications for airport planning","author":"Burghouwt Guillaume","unstructured":"Guillaume Burghouwt . 2016. Airline network development in Europe and its implications for airport planning . Routledge . Guillaume Burghouwt. 2016. Airline network development in Europe and its implications for airport planning. Routledge."},{"key":"e_1_2_1_7_1","volume-title":"Locating pivotal connections: The K-Truss minimization and maximization problems. World Wide Web","author":"Chen Chen","year":"2021","unstructured":"Chen Chen , Mengqi Zhang , Renjie Sun , Xiaoyang Wang , Weijie Zhu , and Xun Wang . 2021. Locating pivotal connections: The K-Truss minimization and maximization problems. World Wide Web ( 2021 ), 1--28. Chen Chen, Mengqi Zhang, Renjie Sun, Xiaoyang Wang, Weijie Zhu, and Xun Wang. 2021. Locating pivotal connections: The K-Truss minimization and maximization problems. World Wide Web (2021), 1--28."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90530-3_8"},{"key":"e_1_2_1_9_1","volume-title":"Michael W Weiner, and Paul M Thompson, for the Alzheimer's Disease Neuroimaging Initiative.","author":"Daianu Madelaine","year":"2013","unstructured":"Madelaine Daianu , Neda Jahanshad , Talia M Nir , Arthur W Toga , Clifford R Jack Jr , Michael W Weiner, and Paul M Thompson, for the Alzheimer's Disease Neuroimaging Initiative. 2013 . Breakdown of brain connectivity between normal aging and Alzheimer's disease: a structural k-core network analysis. Brain connectivity 3, 4 (2013), 407--422. Madelaine Daianu, Neda Jahanshad, Talia M Nir, Arthur W Toga, Clifford R Jack Jr, Michael W Weiner, and Paul M Thompson, for the Alzheimer's Disease Neuroimaging Initiative. 2013. Breakdown of brain connectivity between normal aging and Alzheimer's disease: a structural k-core network analysis. Brain connectivity 3, 4 (2013), 407--422."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3464008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1513876.1513879"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301501"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199410)41:6<833::AID-NAV3220410611>3.0.CO;2-Q"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437963.3441825"},{"key":"e_1_2_1_17_1","first-page":"1287","article-title":"Faster Parallel Core Maintenance Algorithms in Dynamic Graphs","volume":"31","author":"Hua Qiang-Sheng","year":"2019","unstructured":"Qiang-Sheng Hua , Yuliang Shi , Dongxiao Yu , Hai Jin , Jiguo Yu , Zhipen Cai , Xiuzhen Cheng , and Hanhua Chen . 2019 . Faster Parallel Core Maintenance Algorithms in Dynamic Graphs . TPDS 31 , 6 (2019), 1287 -- 1300 . Qiang-Sheng Hua, Yuliang Shi, Dongxiao Yu, Hai Jin, Jiguo Yu, Zhipen Cai, Xiuzhen Cheng, and Hanhua Chen. 2019. Faster Parallel Core Maintenance Algorithms in Dynamic Graphs. TPDS 31, 6 (2019), 1287--1300.","journal-title":"TPDS"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00928ED1V01Y201906DTM061"},{"key":"e_1_2_1_19_1","first-page":"2416","article-title":"Core maintenance in dynamic graphs: A parallel approach based on matching","volume":"29","author":"Jin Hai","year":"2018","unstructured":"Hai Jin , Na Wang , Dongxiao Yu , Qiang-Sheng Hua , Xuanhua Shi , and Xia Xie . 2018 . Core maintenance in dynamic graphs: A parallel approach based on matching . TPDS 29 , 11 (2018), 2416 -- 2428 . Hai Jin, Na Wang, Dongxiao Yu, Qiang-Sheng Hua, Xuanhua Shi, and Xia Xie. 2018. Core maintenance in dynamic graphs: A parallel approach based on matching. TPDS 29, 11 (2018), 2416--2428.","journal-title":"TPDS"},{"key":"e_1_2_1_20_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. 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_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976236.37"},{"key":"e_1_2_1_22_1","volume-title":"Tina Eliassi-Rad, Ali Pinar, and Sucheta Soundarajan.","author":"Laishram Ricky","year":"2018","unstructured":"Ricky Laishram , Ahmet Erdem Sariy\u00fcce , Tina Eliassi-Rad, Ali Pinar, and Sucheta Soundarajan. 2018 . Measuring and improving the core resilience of networks. In WWW. 609--618. Ricky Laishram, Ahmet Erdem Sariy\u00fcce, Tina Eliassi-Rad, Ali Pinar, and Sucheta Soundarajan. 2018. Measuring and improving the core resilience of networks. In WWW. 609--618."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389744"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2985327"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00121"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/480"},{"key":"e_1_2_1_28_1","volume-title":"Gino Del Ferraro, and Hern\u00e1n A Makse","author":"Morone Flaviano","year":"2019","unstructured":"Flaviano Morone , Gino Del Ferraro, and Hern\u00e1n A Makse . 2019 . The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature physics 15 (2019), 95--102. Flaviano Morone, Gino Del Ferraro, and Hern\u00e1n A Makse. 2019. The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature physics 15 (2019), 95--102."},{"key":"e_1_2_1_29_1","volume-title":"Military Communications Conference. 1894--1899","author":"Perumal Senni","year":"2014","unstructured":"Senni Perumal , Prithwish Basu , and Ziyu Guan . 2014 . Minimizing Eccentricity in Composite Networks via Constrained Edge Additions . In Military Communications Conference. 1894--1899 . Senni Perumal, Prithwish Basu, and Ziyu Guan. 2014. Minimizing Eccentricity in Composite Networks via Constrained Edge Additions. In Military Communications Conference. 1894--1899."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11067-010-9131-x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1077-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3040762"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Xin Sun Xin Huang Zitan Sun and Di Jin. 2021. Budget-constrained Truss Maximization over Large Graphs: A Component-based Approach. In CIKM. 1754--1763.  Xin Sun Xin Huang Zitan Sun and Di Jin. 2021. Budget-constrained Truss Maximization over Large Graphs: A Component-based Approach. In CIKM. 1754--1763.","DOI":"10.1145\/3459637.3482324"},{"key":"e_1_2_1_35_1","unstructured":"Dimitrios Vogiatzis. 2013. Influence Study on Hyper-Graphs.. In AAAI Fall Symposia. 24--29.  Dimitrios Vogiatzis. 2013. Influence Study on Hyper-Graphs.. In AAAI Fall Symposia. 24--29."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Kai Wang Xin Cao Xuemin Lin Wenjie Zhang and Lu Qin. 2018. Efficient computing of radius-bounded k-cores. In ICDE. 233--244.  Kai Wang Xin Cao Xuemin Lin Wenjie Zhang and Lu Qin. 2018. Efficient computing of radius-bounded k-cores. In ICDE. 233--244.","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055332"},{"key":"e_1_2_1_38_1","first-page":"245","article-title":"Finding critical users for social network engagement: The collapsed k-core problem","volume":"31","author":"Zhang Fan","year":"2017","unstructured":"Fan Zhang , Ying Zhang , Lu Qin , Wenjie Zhang , and Xuemin Lin . 2017 . Finding critical users for social network engagement: The collapsed k-core problem . In AAAI , Vol. 31. 245 -- 251 . Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI, Vol. 31. 245--251.","journal-title":"AAAI"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115406"},{"key":"e_1_2_1_40_1","volume-title":"Ying Zhang, and Lu Qin.","author":"Zhang Yikai","year":"2017","unstructured":"Yikai Zhang , Jeffrey Xu Yu , Ying Zhang, and Lu Qin. 2017 . A fast order-based approach for core maintenance. In ICDE. 337--348. Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. 2017. A fast order-based approach for core maintenance. In ICDE. 337--348."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Zhiwei Zhang Xin Huang Jianliang Xu Byron Choi and Zechao Shang. 2019. Keyword-centric community search. In ICDE. 422--433.  Zhiwei Zhang Xin Huang Jianliang Xu Byron Choi and Zechao Shang. 2019. Keyword-centric community search. In ICDE. 422--433.","DOI":"10.1109\/ICDE.2019.00045"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-020-00857-0"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Zhongxin Zhou Fan Zhang Xuemin Lin Wenjie Zhang and Chen Chen. 2019. K-Core Maximization: An Edge Addition Approach.. In IJCAI. 4867--4873.  Zhongxin Zhou Fan Zhang Xuemin Lin Wenjie Zhang and Chen Chen. 2019. K-Core Maximization: An Edge Addition Approach.. In IJCAI. 4867--4873.","DOI":"10.24963\/ijcai.2019\/676"},{"key":"e_1_2_1_45_1","volume-title":"VEK: a vertex-oriented approach for edge k-core problem. World Wide Web","author":"Zhou Zhongxin","year":"2021","unstructured":"Zhongxin Zhou , Wenchao Zhang , Fan Zhang , Deming Chu , and Binghao Li. 2021. VEK: a vertex-oriented approach for edge k-core problem. World Wide Web ( 2021 ), 1--18. Zhongxin Zhou, Wenchao Zhang, Fan Zhang, Deming Chu, and Binghao Li. 2021. VEK: a vertex-oriented approach for edge k-core problem. World Wide Web (2021), 1--18."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Weijie Zhu Chen Chen Xiaoyang Wang and Xuemin Lin. 2018. K-core minimization: An edge manipulation approach. In CIKM. 1667--1670.  Weijie Zhu Chen Chen Xiaoyang Wang and Xuemin Lin. 2018. K-core minimization: An edge manipulation approach. In CIKM. 1667--1670.","DOI":"10.1145\/3269206.3269254"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3523210.3523214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:49:35Z","timestamp":1672224575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3523210.3523214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":46,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.14778\/3523210.3523214"],"URL":"https:\/\/doi.org\/10.14778\/3523210.3523214","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}