Abstract
We study the propagation of comparative ideas in social network. A full characterization for submodularity in the comparative independent cascade (Com-IC) model of two-idea cascade is given, for competing ideas and complementary ideas respectively. We further introduce One-Shot model where agents show less patience toward ideas, and show that in One-Shot model, only the stronger idea spreads with submodularity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We say a function \(f: 2^U \rightarrow \mathbb {R}\) is submodular, if for any \(S \subseteq U, a, b \in U\), \(f(S) + f(S \cup \{a, b\}) \le f(S \cup \{a\}) + f(S \cup \{b\})\).
References
Bharathi, S., Kempe, D., Salek, M.: Competitive influence maximization in social networks. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 306–311. Springer, Heidelberg (2007). doi:10.1007/978-3-540-77105-0_31
Borodin, A., Filmus, Y., Oren, J.: Threshold models for competitive influence in social networks. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 539–550. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17572-5_48
Budak, C., Agrawal, D., El Abbadi, A.: Limiting the spread of misinformation in social networks. In: Proceedings of the 20th International Conference on World Wide Web, pp. 665–674. ACM (2011)
Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rincon, D., Sun, X., Wang, Y., Wei, W., Yuan, Y.: Influence maximization in social networks when negative opinions may emerge and propagate. In: SDM, vol. 11, pp. 379–390. SIAM (2011)
Datta, S., Majumder, A., Shrivastava, N.: Viral marketing for multiple products. In: 2010 IEEE International Conference on Data Mining, pp. 118–127. IEEE (2010)
He, X., Song, G., Chen, W., Jiang, Q.: Influence blocking maximization in social networks under the competitive linear threshold model. In: SDM, pp. 463–474. SIAM (2012)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM (2003)
Lu, W., Bonchi, F., Goyal, A., Lakshmanan, L.V.: The bang for the buck: fair competitive viral marketing from the host perspective. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 928–936. ACM (2013)
Lu, W., Chen, W., Lakshmanan, L.V.: From competition to complementarity: comparative influence diffusion and maximization. Proc. VLDB Endow. 9(2), 60–71 (2015)
Narayanam, R., Nanavati, A.A.: Viral marketing for product cross-sell through social networks. In: Flach, P.A., Bie, T., Cristianini, N. (eds.) ECML PKDD 2012. LNCS, vol. 7524, pp. 581–596. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33486-3_37
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions–I. Math. Program. 14(1), 265–294 (1978)
Acknowledgment
We would like to thank Yingru Li for some early discussions on the subject.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Chen, W., Zhang, H. (2017). Complete Submodularity Characterization in the Comparative Independent Cascade Model. In: Xiao, M., Rosamond, F. (eds) Frontiers in Algorithmics. FAW 2017. Lecture Notes in Computer Science(), vol 10336. Springer, Cham. https://doi.org/10.1007/978-3-319-59605-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-59605-1_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59604-4
Online ISBN: 978-3-319-59605-1
eBook Packages: Computer ScienceComputer Science (R0)