.png){kind=icon}
.png){kind=icon}
Return
Complementary influence maximization under comparative linear threshold model
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2023.121826.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The influence maximization problem asks to find a small number of early adopters of a product in a social network, such that the expected number of total adoptions is maximized over the network. The problem has been well-studied, but most of the studies focus on the case of a single product or purely competitive products. This paper proposes a new influence diffusion model for multiple complementary products, namely, the comparative linear threshold (Com-LT) model. Under the Com-LT model, we model the complementary relation by reducing the thresholds of nodes. With this model, we study two problems: SelfInfMax and CompInfMax. We prove that these two problems are both NP-Hard under the Com-LT model. For both the SelfInfMax and the CompInfMax problem, we theoretically analyze the monotonicity and submodularity, and accordingly leverage lower bound optimization to devise non-trivial effective approximation algorithms. We conduct experiments over 4 real-world datasets. The experimental results demonstrate the correctness and efficiency of the proposed algorithms.
Keywords:
Comparative linear threshold
Complementary influence maximization
Reverse influence sampling
Lower bound optimization
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W