Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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–539
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–18
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–108
Acknowledgments
This work is supported in part by National Natural Science Foundation of China under 61472272 and Shanxi Province science research project under Grant No. 20130313030-1.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, A., Wu, W. & Cui, L. On Bharathi–Kempe–Salek conjecture for influence maximization on arborescence. J Comb Optim 31, 1678–1684 (2016). https://doi.org/10.1007/s10878-016-9991-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-9991-1