Anchored Maximum Communities over Large Directed Graphs

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.