{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:00:36Z","timestamp":1774983636246,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    The ((\n                    <jats:italic toggle=\"yes\">k,p<\/jats:italic>\n                    ))-core model was recently proposed to capture engagement dynamics by considering both intra-community interactions (i.e., the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core structure) and inter-community interactions (i.e., the\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    -fraction property). It is a refinement of the classic\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core, by introducing an extra parameter\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    to customize the engagement within a community at a finer granularity. In this paper, we study the problem of maintaining all (k,p)-cores (essentially, maintaining the p-numbers for all vertices) for dynamic graphs. The existing Global approach conducts a global peeling, almost from scratch, for all vertices whose old p-numbers are within a computed range [p\n                    <jats:sub>-<\/jats:sub>\n                    ,p\n                    <jats:sub>+<\/jats:sub>\n                    ], and thus is inefficient. We propose a new Local approach which conducts local searches starting from the two end-points of the newly inserted or deleted edge, and then iteratively expands the search frontier by including their neighbors. Our algorithm is designed based on several fundamental properties that we prove in this paper to characterize the necessary condition for a vertex's p-number to change. Compared to Global, our Local approach implicitly obtains the optimal affected p-number range [p\n                    <jats:sub>-<\/jats:sub>\n                    <jats:sup>*<\/jats:sup>\n                    ,p\n                    <jats:sub>+<\/jats:sub>\n                    <jats:sup>*<\/jats:sup>\n                    ] \u2286 [p\n                    <jats:sub>-<\/jats:sub>\n                    ,p\n                    <jats:sub>+<\/jats:sub>\n                    ], and further skips many vertices whose p-numbers are within this range. Experimental results show that Local is on average two orders of magnitude faster than Global.\n                  <\/jats:p>","DOI":"10.1145\/3709654","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["A Local Search Approach to Efficient (\n                    <i>k,p<\/i>\n                    )-Core Maintenance"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5412-4192","authenticated-orcid":false,"given":"Chenghan","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3422-8017","authenticated-orcid":false,"given":"Yuanyuan","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"School of Computer Science, The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137640"},{"key":"e_1_2_1_2_1","volume-title":"Towards a science of user engagement (Position Paper). (01","author":"Attfield Simon","year":"2011","unstructured":"Simon Attfield, Gabriella Kazai, Mounia Lalmas, and Benjamin Piwowarski. 2011. Towards a science of user engagement (Position Paper). (01 2011)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--59416--9_42"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566421"},{"key":"e_1_2_1_5_1","unstructured":"V. Batagelj and M. Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. arxiv: cs\/0310049 [cs.DS]"},{"key":"e_1_2_1_6_1","first-page":"1452","article-title":"Preventing Unraveling in Social Networks: The Anchored k-Core Problem","volume":"29","author":"Bhawalkar Kshipra","year":"2015","unstructured":"Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. 2015. Preventing Unraveling in Social Networks: The Anchored k-Core Problem. SDM, Vol. 29, 3 (2015), 1452--1475.","journal-title":"SDM"},{"key":"e_1_2_1_7_1","volume-title":"Ajmal Mian, John Yearwood, and Timos Sellis.","author":"Cai Taotao","year":"2020","unstructured":"Taotao Cai, Jianxin Li, Nur Al Hasan Haldar, Ajmal Mian, John Yearwood, and Timos Sellis. 2020. Anchored Vertex Exploration for Community Engagement in Social Networks. In ICDE. 409--420."},{"key":"e_1_2_1_8_1","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report Vol. 16 (2008)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Cristian Danescu-Niculescu-Mizil Robert West Dan Jurafsky Jure Leskovec and Christopher Potts. 2013. No country for old members: User lifecycle and linguistic change in online communities. In WWW. 307--318.","DOI":"10.1145\/2488388.2488416"},{"key":"e_1_2_1_10_1","first-page":"53","article-title":"Social media engagement theory: Exploring the influence of user engagement on social media usage","volume":"28","author":"Di Gangi Paul M","year":"2016","unstructured":"Paul M Di Gangi and Molly M Wasko. 2016. Social media engagement theory: Exploring the influence of user engagement on social media usage. JOEUC, Vol. 28, 2 (2016), 53--73.","journal-title":"JOEUC"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018478"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0247018"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"David Garcia Pavlin Mavrodiev and Frank Schweitzer. 2013. Social resilience in online communities: the autopsy of friendster. In OSN. 39--50.","DOI":"10.1145\/2512938.2512946"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep39467"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Liangjie Hong and Mounia Lalmas. 2020. Tutorial on Online User Engagement: Metrics and Optimization.. In SIGKDD. 3551--3552.","DOI":"10.1145\/3394486.3406472"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Xin Huang Hong Cheng Lu Qin Wentao Tian and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In SIGMOD. 1311--1322.","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00605ED1V01Y201410ICR038"},{"key":"e_1_2_1_20_1","volume-title":"Lakshmanan","author":"Lee Pei","year":"2016","unstructured":"Pei Lee and Laks V. S. Lakshmanan. 2016. Query-Driven Maximum Quasi-Clique Search. In ICDM. 522--530."},{"key":"e_1_2_1_21_1","first-page":"757","article-title":"Hierarchical core maintenance on large dynamic graphs","volume":"14","author":"Lin Zhe","year":"2021","unstructured":"Zhe Lin, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Zhihong Tian. 2021. Hierarchical core maintenance on large dynamic graphs. In VLDB, Vol. 14. 757--770.","journal-title":"VLDB"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00109"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Qi Luo Dongxiao Yu Hao Sheng Jiguo Yu and Xiuzhen Cheng. 2020. Distributed Algorithm for Truss Maintenance in Dynamic Graphs.. In PDCTA. 104--115.","DOI":"10.1007\/978-3-030-69244-5_9"},{"key":"e_1_2_1_24_1","volume-title":"Malliaros and Michalis Vazirgiannis","author":"Fragkiskos","year":"2013","unstructured":"Fragkiskos D. Malliaros and Michalis Vazirgiannis. 2013. To stay or not to stay: modeling engagement dynamics in social graphs. In CIKM. 469--478."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0304--8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00121"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1162\/netn_a_00169"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27446-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In SIGKDD. 939--948.","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Chenhao Tan and Lillian Lee. 2015. All who wander: On the prevalence and characteristics of multi-community engagement. In WWW. 1056--1066.","DOI":"10.1145\/2736277.2741661"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1116502109"},{"key":"e_1_2_1_34_1","first-page":"129","article-title":"Efficient Distributed Approaches to Core Maintenance on Large Dynamic Graphs","volume":"33","author":"Weng Tongfeng","year":"2022","unstructured":"Tongfeng Weng, Xu Zhou, Kenli Li, Peng Peng, and Keqin Li. 2022. Efficient Distributed Approaches to Core Maintenance on Large Dynamic Graphs. TPDS, Vol. 33, 1 (2022), 129--143.","journal-title":"TPDS"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570701"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Chen Zhang Fan Zhang Wenjie Zhang Boge Liu Ying Zhang Lu Qin and Xuemin Lin. 2020. Exploring Finer Granularity within the Cores: Efficient (k p)-Core Computation. In ICDE. 181--192.","DOI":"10.1109\/ICDE48307.2020.00023"},{"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":"998","article-title":"When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks","volume":"10","author":"Zhang Fan","year":"2017","unstructured":"Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks. VLDB, Vol. 10, 10 (2017), 998--1009.","journal-title":"VLDB"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Fan Zhang Ying Zhang Lu Qin Wenjie Zhang and Xuemin Lin. 2018. Efficiently Reinforcing Social Networks over User Engagement and Tie Strength. In ICDE. 557--568.","DOI":"10.1109\/ICDE.2018.00057"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2023.113941"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2019. Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs. In SIGMOD. 1024--1041.","DOI":"10.1145\/3299869.3300082"},{"key":"e_1_2_1_42_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."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709654","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:16:24Z","timestamp":1774980984000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709654"],"URL":"https:\/\/doi.org\/10.1145\/3709654","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}