{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:04:29Z","timestamp":1775595869434,"version":"3.50.1"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    Influential community (IC) search has gained much attention with applications in many areas, such as event organization, recommendation systems, and biological analysis. The dynamic nature of graphs, with frequent insertions and deletions of vertices and edges, makes searching ICs over dynamic graphs computationally costly. To enable efficient IC search on large graphs, existing works often develop index-based approaches, which first compute all the ICs, a.k.a. IC decomposition, and then organize them into some index structures compactly. However, designed for static graphs, these index structures cannot be maintained efficiently for dynamic graphs, and little attention has been paid to the theoretical analysis of the index maintenance algorithms. To tackle the above issues, in this paper, we study the IC search problem on large dynamic graphs, and maintain the index structures efficiently by developing novel IC maintenance algorithms. We first theoretically show that all existing index maintenance algorithms, for the scenarios of both edge insertion and deletion, are relatively unbounded. We then propose a novel concept, called\n                    <jats:italic toggle=\"yes\">IC decomposition order (ICD-order),<\/jats:italic>\n                    based on which we further develop novel efficient IC maintenance algorithms for the scenarios of edge insertions and deletions, respectively. These algorithms not only effectively reduce the scope of affected vertices for improving efficiency, but also offer more favorable time complexities. The comprehensive experiments on eight real datasets show that our algorithms are up to six and three orders of magnitude faster than state-of-the-art index maintenance algorithms under the edge insertion and deletion scenarios, respectively.\n                  <\/jats:p>","DOI":"10.1145\/3786644","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-28","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Influential Community Search over Dynamic Graphs"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-1371-666X","authenticated-orcid":false,"given":"Youran","family":"Sun","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5630-6822","authenticated-orcid":false,"given":"Yingli","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1348-4388","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2622-4075","authenticated-orcid":false,"given":"Cheng","family":"Chen","sequence":"additional","affiliation":[{"name":"ByteDance Inc, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1041-1748","authenticated-orcid":false,"given":"Yongmin","family":"Hu","sequence":"additional","affiliation":[{"name":"ByteDance Inc, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1345-074X","authenticated-orcid":false,"given":"Yingqian","family":"Hu","sequence":"additional","affiliation":[{"name":"ByteDance Inc, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_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)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213881"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.20609"},{"key":"e_1_2_1_6_1","volume-title":"The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems","author":"Brin Sergey","year":"1998","unstructured":"Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, Vol. 30, 1-7 (1998), 107-117."},{"key":"e_1_2_1_7_1","volume-title":"Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics","author":"Brohee Sylvain","year":"2006","unstructured":"Sylvain Brohee and Jacques Van Helden. 2006. Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics, Vol. 7 (2006), 1-19."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498245"},{"key":"e_1_2_1_9_1","first-page":"459","article-title":"Index-based optimal algorithms for computing steiner components with maximum connectivity","author":"Chang Lijun","year":"2015","unstructured":"Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Wenjie Zhang. 2015. Index-based optimal algorithms for computing steiner components with maximum connectivity. In SIGMOD. 459-474.","journal-title":"SIGMOD."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225063"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_2_1_12_1","first-page":"1553","article-title":"Efficient computation of importance based communities in web-scale networks using a single machine","author":"Chen Shu","year":"2016","unstructured":"Shu Chen, Ran Wei, Diana Popova, and Alex Thomo. 2016. Efficient computation of importance based communities in web-scale networks using a single machine. In CIKM. 1553-1562.","journal-title":"CIKM."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_14_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report, Vol. 16, 3.1 (2008)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2013.11.015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.175.0420"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.027104"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.11"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223849"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_34_1","volume-title":"Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations.","author":"Thomas","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2019.10.004"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jspi.2007.04.011"},{"key":"e_1_2_1_37_1","volume-title":"Dynamic Spectral Clustering with Provable Approximation Guarantee. In Forty-first International Conference on Machine Learning.","author":"Laenen Steinar","year":"2024","unstructured":"Steinar Laenen and He Sun. 2024. Dynamic Spectral Clustering with Provable Approximation Guarantee. In Forty-first International Conference on Machine Learning."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/188"},{"key":"e_1_2_1_39_1","first-page":"457","article-title":"Skyline Community Search in Multi-valued Networks","author":"Li Rong-Hua","year":"2018","unstructured":"Rong-Hua Li, Lu Qin, Fanghua Ye, Jeffrey Xu Yu, Xiaokui Xiao, Nong Xiao, and Zibin Zheng. 2018. Skyline Community Search in Multi-valued Networks. In SIGMOD. ACM, 457-472.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00618-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0467-4"},{"key":"e_1_2_1_43_1","volume-title":"Jeffrey Xu Yu, and Rui Mao","author":"Li Rong-Hua","year":"2013","unstructured":"Rong-Hua Li, Jeffrey Xu Yu, and Rui Mao. 2013. Efficient core maintenance in large dynamic graphs. IEEE transactions on knowledge and data engineering, Vol. 26, 10 (2013), 2453-2465."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659440"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00016"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588725"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3131611"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2020.3021488"},{"key":"e_1_2_1_50_1","volume-title":"International Conference on Machine Learning. PMLR, 3423-3432","author":"Martin Lionel","year":"2018","unstructured":"Lionel Martin, Andreas Loukas, and Pierre Vandergheynst. 2018. Fast approximate spectral clustering for dynamic networks. In International Conference on Machine Learning. PMLR, 3423-3432."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00257"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.24"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00191"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.016110"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452828"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598561"},{"key":"e_1_2_1_61_1","first-page":"699","article-title":"Ranking-based clustering on general heterogeneous information networks by network projection","author":"Shi Chuan","year":"2014","unstructured":"Chuan Shi, Ran Wang, Yitong Li, Philip S Yu, and Bin Wu. 2014. Ranking-based clustering on general heterogeneous information networks by network projection. In CIKM. 699-708.","journal-title":"CIKM."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_63_1","volume-title":"Relation strength-aware clustering of heterogeneous information networks with incomplete attributes. arXiv preprint arXiv:1201.6563","author":"Sun Yizhou","year":"2012","unstructured":"Yizhou Sun, Charu C Aggarwal, and Jiawei Han. 2012. Relation strength-aware clustering of heterogeneous information networks with incomplete attributes. arXiv preprint arXiv:1201.6563 (2012)."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516426"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500492"},{"key":"e_1_2_1_66_1","first-page":"797","article-title":"Ranking-based clustering of heterogeneous information networks with star network schema","author":"Sun Yizhou","year":"2009","unstructured":"Yizhou Sun, Yintao Yu, and Jiawei Han. 2009b. Ranking-based clustering of heterogeneous information networks with star network schema. In KDD. 797-806.","journal-title":"KDD."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.237"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457278"},{"key":"e_1_2_1_69_1","volume-title":"Graph Attention Networks. In International Conference on Learning Representations.","author":"Veli\u010dkovi\u0107 Petar","year":"2018","unstructured":"Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00541-4"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.25"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-021-00163-3"},{"key":"e_1_2_1_73_1","unstructured":"Xiaoliang Xu Jun Liu Yuxiang Wang and Xiangyu Ke. 2022. Academic Expert Finding via (K P)-Core based Embedding over Heterogeneous Graphs. In ICDE."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_1_75_1","first-page":"901","article-title":"Effective and efficient truss computation over large heterogeneous information networks","author":"Yang Yixing","year":"2020","unstructured":"Yixing Yang, Yixiang Fang, Xuemin Lin, and Wenjie Zhang. 2020. Effective and efficient truss computation over large heterogeneous information networks. In ICDE. IEEE, 901-912.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551840"},{"key":"e_1_2_1_79_1","first-page":"1024","article-title":"Unboundedness and efficiency of truss maintenance in evolving graphs","author":"Zhang Yikai","year":"2019","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2019. Unboundedness and efficiency of truss maintenance in evolving graphs. In SIGMOD. 1024-1041.","journal-title":"SIGMOD."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594532"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681975"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677129"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487640"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:01:14Z","timestamp":1775592074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":84,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786644"],"URL":"https:\/\/doi.org\/10.1145\/3786644","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}