Paper Info
Title
Minimum cost seed set for threshold influence problem under competitive models
Abstract
Single source influence propagation based models have been widely studied, but a key challenge remains: How does a company utilize the minimum cost to select a seed set such that its influence spread can reach a desired threshold in competitive environment. One efficient way to overcome this challenge is to design an influence spread function with monotonicity and submodularity, which can provide a nice theoretical analysis of approximation ratio. In this paper, we first propose the Threshold Influence (TI) problem, i.e., selecting a seed set with minimum cost such that the influence spread reaches a given threshold η. Then we present two influence diffusion models named One-To-Many (OTM) and One-To-One (OTO) respectively. On one hand, for One-To-Many model, we prove that the influence spread function is monotone increasing as well as submodular and develop a greedy algorithm with a \((1+\ln (\frac {\eta }{\delta }))\) approximation ratio, where \(\delta >0\). In particular, the approximation ratio is (\(1+\ln (\eta )\)) if \(\eta \) is a positive integer. On the other hand, for One-To-One model, we demonstrate that the influence spread function is non-submodular. Besides, a heuristic framework is developed to solve this problem. Finally, we evaluate our algorithms by simulations on different scale networks. Through experiments, our algorithms outperform comparative methods.
Year
DOI
Venue
2019
10.1007/s11280-018-0607-9
World Wide Web
Keywords
Field
DocType
Competitive influence, Diffusion model, Seed selection, Submodularity
Integer,Monotonic function,Data mining,Discrete mathematics,Heuristic,Influence propagation,Computer science,Submodular set function,Greedy algorithm,Diffusion (business),Monotone polygon
Journal
Volume
Issue
ISSN
22
6
1573-1413
Citations 
PageRank 
References 
1
0.36
13
Authors
4
Name
Order
Citations
PageRank
Ruidong Yan1103.89
Zhu Yuqing246737.26
Deying Li350.77
Zilong Ye47811.97