The most influenced community search on social networks

Publication Type

Conference Proceeding Article

Publication Date

5-2025

Abstract

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.

Discipline

Databases and Information Systems | Digital Communications and Networking

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 2025 IEEE 41st International Conference on Data Engineering (ICDE), Hong Kong, May 19-23

First Page

2601

Last Page

2614

Identifier

10.1109/ICDE65448.2025.00196

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

This document is currently not available here.

Share

COinS