科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 eta. 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(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.
- 出版日期2019-11
- 单位中国人民大学
