On Bharathi–Kempe–Salek conjecture for influence maximization on arborescence

详细信息    查看全文

• 作者：Ailian Wang ; Weili Wu ; Lei Cui
• 关键词：Bharathi–Kempe–Salek conjecture ; Influence maximization ; In ; arborescence ; Independent cascade (IC) model ; Linear threshold Model
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1678-1684
• 全文大小：413 KB
• 参考文献：Bharathi S, Kempe D, Salek M (2007) Competitive influence maximization in social networks. In: WINE, pp 306–311
  Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: The 2010 international conference on data mining
  Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: The 2010 ACM SIGKDD conference on knowledge discovery and data mining
  Chen N (2008) On the approximability of influence in social networks. In: The 2008 annual ACM SIAM symposium on discrete algorithms, pp 1029–1037
  Fan L, Lu Zaixin, Wu Weili, Bi Y, Wang A, Thuraisingham BM (2014) An individual-based model of information diffusion combining friends’ influence. J Comb Optim 28(3):529–539MathSciNet CrossRef MATH
  He X, Kempe D (2014) Stability of influence maximization. In: KDD, pp 1256–1265
  Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of infuence through a social network. In: The 2003 international conference on knowledge discovery and data mining, pp 137–146
  Kempe D, Kleinberg J, Tardos E (2005) Influential nodes in a diffusion model for social networks. In: The 2005 international colloquium on automata, languages and programming, pp 1127–1138
  Lu Z, Zhang W, Wu W, Fu B, Du D-Z (2011) Approximation and inapproximation for the influence maximization problem in social networks under deterministic linear threshold model. In: ICDCS workshops, pp 160–165
  Lu Z, Zhu Y, Li W, Wu W, Cheng X (2014) Influence-based community partition for social networks. Comput Soc Netw 1:1–18CrossRef
  Tong G, Wu W, Tang S, Du D-Z (2015) Adaptive influence maximization in dynamic social networks. CoRR abs/1506.06294
  Xu W, Lu Z, Wu W, Chen Z (2014) A novel approach to online social influence maximization. Soc Netw Anal Min 4(1):153
  Zhu Y, Wu W, Bi Y, Wu L, Jiang Y, Wen X (2015) Better approximation algorithms for influence maximization in online social networks. J Comb Optim 30(1):97–108MathSciNet CrossRef MATH
  
• 作者单位：Ailian Wang (1)
  Weili Wu (1) (2)
  Lei Cui (2)
  
  1. Taiyuan University of Technology, Shanxi, 030024, China
  2. Department of Computer Science, University of Texas at Dallas, Richardson, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Bharathi et al. (WINE, pp 306–311, 2007) conjectured that the influence maximization problem is NP-hard for arborescence directed into a root. In this note, we show that this conjecture is not true for deterministic diffusion model and linear threshold (LT) model, that is, there exist polynomial-time algorithms for the influence maximization problem in those two models on arborescence directed into a root. This means that if the conjecture in the independent cascade (IC) model is true, then it would give an interesting difference between the IC model and the LT model.