Anchored Maximum Communities over Large Directed Graphs
Proceedings of the VLDB Endowment · 01.02.2026 · 19 (6) · 1345-1357
DOI: 10.14778/3797919.3797939 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 08.05.2026. Verfasst von Yang Huang und 5 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben.
Abstract (Originalsprache)
User engagement is a powerful tool that analyzes the expansion or unraveling of social networks. There have been many researches on user engagement to anchor critical users for enhancing engagement. However, these researches neglect the inherent directed nature of real-world social networks, such as the unidirectional follower relationships on platforms like X (Twitter). Motivated by this, we introduce the Anchored ( k,l )- Core Maximization (ADCM) problem over directed graphs for the first time. Given a directed graph G , degree constraints k and l , and a budget b , the goal is to find b vertices in G , whose sustained engagement can maximize the ( k,l )-core. We prove the NP-hardness of the ADCM problem and propose the Greedy-based algorithm (Greedy-based) to process it effectively. After that, to mitigate the isolation effect caused by greediness, a vertex scoring function is designed to support core expansion. To boost the computational performance, we develop pruning techniques, candidate reduction strategies, and an upper-bound-based termination criterion, based on which we design the Fast Anchor D-core (FAD) algorithm. Extensive experiments on eight real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms. From experimental results, FAD achieves over 1000× speedup compared to Greedy-based when b > 3.
Zitieren
APA
Huang, Y., Zhou, X., Ding, Y., Liu, Q., Xu, H., & Li, K. (2026). Anchored Maximum Communities over Large Directed Graphs. Proceedings of the VLDB Endowment, 19(6), 1345-1357. https://doi.org/10.14778/3797919.3797939
Vancouver
Huang Y, Zhou X, Ding Y, Liu Q, Xu H, Li K. Anchored Maximum Communities over Large Directed Graphs. Proceedings of the VLDB Endowment. 2026;19(6):1345-1357. doi:10.14778/3797919.3797939
BibTeX
@article{Huang2026,
author = {Huang, Yang and Zhou, Xu and Ding, Yan and Liu, Qing and Xu, Haoxian and Li, Kenli},
title = {Anchored Maximum Communities over Large Directed Graphs},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {6},
pages = {1345--1357},
doi = {10.14778/3797919.3797939}
}
EUVIMED