The Most Influenced Community Search on Social Networks

In this paper, we address a novel problem in social network analysis: the Most Influenced Community Search (MICS). Given a graph and a seed node set$S$, the MICS problem seeks to identify a densely connected sub graph that is most significantly impacted by$S$. We formally define MICS, prove its NP-hardness, and show that constant-factor approximation is not feasible. To solve MICS efficiently, we propose a two-phase framework. In the first phase, we compute the influenced expectation for each node, representing its likelihood of being influenced by$S$. We develop two algorithms: S-InfExp, a sampling-based method with theoretical guarantees, and L-InfExp, a learning-based approach for faster predictions. In the second phase, we introduce two algorithms, GlobalSearch and LocalSearch, to find the most influenced community. GlobalSearch uses a top-down, greedy approach, while LocalSearch applies a bottom-up strategy. Experiments on eight real-world datasets demonstrate that (1) L-InfExp is up to 100× faster than S-InfExp with comparable accuracy, (2) LocalSearch is 10× faster than GlobalSearch, with both algorithms effectively identifying the community with the highest influenced expectations, and (3) our algorithms outperform all baselines.