Supplementary Influence Maximization Problem in Social Networks

Bibliographic Data

ID22107312
AuthorsYapu Zhang (0000-0001-5122-4854, Beijing University of Technology), Jianxiong Guo (0000-0002-0994-3297, Beijing Normal-Hong Kong Baptist University), Wenguo Yang (0000-0002-8441-7334, University of Chinese Academy of Sciences), Weili Wu (0000-0001-8747-6340, The University of Texas at Dallas)
Year2024
Volume11
Issue1
Pages986-996
Publication date2024-02-01
Open AccessYes
TypeARTICLE
VenueIEEE Transactions on Computational Social Systems (JOURNAL)
Journal identifiersISSN: 2329-924X • E-ISSN: 2373-7476
PublisherInstitute of Electrical and Electronics Engineers (IEEE) (PUBLISHER)
DOI10.1109/tcss.2023.3234437
OpenAlexW4313855755
LanguageEN
Citations received2
References cited30

Due to important applications in viral marketing, influence maximization (IM) has become a well-studied problem. It aims at finding a small subset of initial users so that they can deliver information to the largest amount of users through the word-of-mouth effect. The original IM only considers a singleton item. And the majority of extensions ignore the relationships among different items or only consider their competitive interactions. In reality, the diffusion probability of one item will increase when users adopted supplementary products in advance. Motivated by this scenario, we propose a supplementary independent cascade (IC) and discuss the supplementary IM problem. Our problem is NP-hard, and the computation of the objective function is #P-hard. We notice that the diffusion probability will change when considering the impact of its supplementary product. Therefore, the efficient reverse influence sampling (RIS) techniques cannot be applied to our problem directly even though the objective function is submodular. To address this issue, we utilize the sandwich approximation (SA) strategy to obtain a data-dependent approximate solution. Furthermore, we define the supplementary-based reverse reachable (SRR) sets and then propose a heuristic algorithm. Finally, the experimental results on three real datasets support the efficiency and superiority of our methods

Algorithm · Approximation algorithm · Heuristic · Mathematical optimization · Maximization · Notice · Social media · Submodular set function · Viral marketing · Complex Network Analysis Techniques · Computer Science · Mathematics · Opinion Dynamics and Social Influence · Spam and Phishing Detection · Artificial Intelligence · Theoretical Computer Science

Tools

Open DOI