Back to Search
Start Over
Complementary influence maximization under comparative linear threshold model.
- Source :
-
Expert Systems with Applications . Mar2024:Part D, Vol. 238, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- 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. • We study the complementary version of the influence maximization problem. • We propose Com-LT model to describe the influence spread of non- competitive products. • We studied the SelfInfMax and the CompInfMax problem and show their hardness. • We propose approximation algorithms with high quality feasible solutions. • We conduct experiments on real networks and show the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SOCIAL networks
*APPROXIMATION algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 09574174
- Volume :
- 238
- Database :
- Academic Search Index
- Journal :
- Expert Systems with Applications
- Publication Type :
- Academic Journal
- Accession number :
- 173706053
- Full Text :
- https://doi.org/10.1016/j.eswa.2023.121826