Influence Maximization (IM) problem is to select influential users to maximize the influence spread, which plays an important role in many real-world applications such as product recommendation, epidemic control, and network monitoring. Nowadays multiple kinds of information can propagate in online social networks simultaneously, but current literature seldom discuss about this phenomenon. Accordingly, in this article, we propose Multiple Influence Maximization (MIM) problem where multiple information can propagate in a single network with different propagation probabilities. The goal of MIM problems is to maximize the overall accumulative influence spreads of different information with the limit of seed budget . To solve MIM problems, we first propose a greedy framework to solve MIM problems which maintains an -approximate ratio. We further propose parallel algorithms based on semaphores, an inter-thread communication mechanism, which significantly improves our algorithms efficiency. Then we conduct experiments for our framework using complex social network datasets with 12k, 154k, 317k, and 1.1m nodes, and the experimental results show that our greedy framework outperforms other heuristic algorithms greatly for large influence spread and parallelization of algorithms reduces running time observably with acceptable memory overhead.
Parallel Greedy Algorithm to Multiple Influence Maximization in Social Network
Guanhao Wu,Xiaofeng Gao,Ge Yan,Guihai Chen
Published 2021 in ACM Transactions on Knowledge Discovery from Data
ABSTRACT
PUBLICATION RECORD
- Publication year
2021
- Venue
ACM Transactions on Knowledge Discovery from Data
- Publication date
2021-04-21
- Fields of study
Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
- No claims are published for this paper.
CONCEPTS
- No concepts are published for this paper.
REFERENCES
Showing 1-42 of 42 references · Page 1 of 1
CITED BY
Showing 1-26 of 26 citing papers · Page 1 of 1