Abstract
Influence maximization is an important problem in social networks. Bharathi et al. (Competitive influence maximization in social networks, pp 306–311, 2007) conjectured that this problem is \({{\mathcal {N}}}{{\mathcal {P}}}\)-hard on arborescence directed into a root. In this short note, we show that the conjecture is true for the independent cascade (IC) model, which is the most studied model in the literature specifying how each node influences other nodes. Therefore, assuming \({\mathcal {P}}\ne {{\mathcal {N}}}{{\mathcal {P}}}\), there exists no polynomial-time algorithm for the influence maximization problem under the IC model on arborescence directed into a root. On the other hand, Wang et al. (J Comb Optim, doi:10.1007/s10878-016-9991-1, 2016) have shown that there exists polynomial-time algorithm for this problem under the linear threshold (LT) model. Hence, this pair of results is of theoretical interest since this is the first time to give a theoretical difference on computational complexity between the IC and LT models. We believe it may motivate further research for influence maximization on arborescence and other special graphs.
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
Brown J, Reinegen P (1987) Social ties and word-of-mouth referral behavior. J Consum Res 14:350–362
Chen N (2008) On the approximability of influence in social networks. In: The 2008 annual ACM SIAM symposium on Discrete algorithms, pp 1029–1037
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: KDD
Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: ICDM
Domingos P, Richardson M (2001) Mining the network value of customers. In: KDD, pp 57–66
Fan L, Lu Z, Wu W, Bi Y, Wang A, Thuraisingham B (2014) An individual-based model of information diffusion combining friends’ influence. J Comb Optim 28(3):529–539
Goldenberg J, Libai B, Muller E (2001a) Talk of the network: a complex systems look at the underlying process of word-of-mouth. Mark Lett 12:211–223
Goldenberg J, Libai B, Muller E (2001b) Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata. Acad Mark Sci Rev 2001:1
Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443
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: KDD, pp 137–146
Kempe D, Kleinberg J, Tardos E (2005) Influential nodes in a diffusion model for social networks. In: 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
Richardson M, Domingos V (2002) Mining knowledge-sharing sites for viral marketing. In: KDD, pp 61–70
Schelling T (1978) Micromotives and macrobehavior. Norton, New York
Tong G, Wu W, Tang S, Du D-Z (2015) Adaptive influence maximization in dynamic social networks. CoRR. arXiv:1506.06294
Wang A, Wu W, Cui L (2016) On Bharathi-Kempe-Salek conjecture for influence maximization on arborescence. J Comb Optim. doi:10.1007/s10878-016-9991-1
Xu Wen Lu, Weili Zaixin, Wu, Zhiming Chen (2014) A novel approach to online social influence maximization. Soc Netw Anal Min 4(1):153
Acknowledgments
This work is supported in part by National Natural Science Foundation of China under (61472272, 11531011), and Xinjiang Talent Youth Project (2013711011).
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Lu, Z., Zhang, Z. & Wu, W. Solution of Bharathi–Kempe–Salek conjecture for influence maximization on arborescence. J Comb Optim 33, 803–808 (2017). https://doi.org/10.1007/s10878-016-0006-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0006-z