Capacity Constrained Influence Maximization in Social Networks

Shiqi Zhang1,2; Yiqian Huang2; Jiachen Sun3; Wenqing Lin3; Xiaokui Xiao1; Bo Tang2

10.1145/3580305.3599267

2023

29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

PROCEEDINGS OF THE 29TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, KDD 2023

AUG 06-10, 2023

null,Long Beach,CA

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

Influence maximization (IM) aims to identify a small number of influential individuals to maximize the information spread and finds applications in various fields. It was first introduced in the context of viral marketing, where a company pays a few influencers to promote the product. However, apart from the cost factor, the capacity of individuals to consume content poses challenges for implementing IM in real-world scenarios. For example, players on online gaming platforms can only interact with a limited number of friends. In addition, we observe that in these scenarios, (i) the initial adopters of promotion are likely to be the friends of influencers rather than the influencers themselves, and (ii) existing IM solutions produce sub-par results with high computational demands. Motivated by these observations, we propose a new IM variant called capacity constrained influence maximization (CIM), which aims to select a limited number of influential friends for each initial adopter such that the promotion can reach more users. To solve CIM effectively, we design two greedy algorithms, MG-Greedy and RR-Greedy, ensuring the 1/2-approximation ratio. To improve the efficiency, we devise the scalable implementation named RR-OPIM+ with (1/2 - epsilon)-approximation and near-linear running time. We extensively evaluate the performance of 9 approaches on 6 real-world networks, and our solutions outperform all competitors in terms of result quality and running time. Additionally, we deploy RR-OPIM+ to online game scenarios, which improves the baseline considerably.

influence maximization greedy algorithm online gaming platform

通讯

英语

EI ; CPCI-S

Singapore Ministry of Education Academic Research Fund Tier 3[MOE2017-T3-1-007] ; Proxima Beta[A-8000177-00-00] ; Shenzhen Fundamental Research Program[20220815112848002]

Computer Science

Computer Science, Information Systems ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods

WOS:001118896303038

Web of Science

1.National University of Singapore
2.Southern University of Science and Technology
3.Tencent

Shiqi Zhang,Yiqian Huang,Jiachen Sun,et al. Capacity Constrained Influence Maximization in Social Networks[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023.