We consider revenue maximization in viral marketing of competitive and collaborative products through social networks, focusing on the word-of-mouth effect on personal decisions in adopting products, technologies, or Internet applications. In our model, each advertiser submits its value per consumer, and its total budget. The publisher pays a selected set of users on social networks as seed nodes. It demands a payment (equal to its value) from an advertiser for each influenced node in social networks. The publisher's revenue equals to the total payment from the influenced users minus its cost of seed nodes.In this paper,we study the efficient allocation problem of the publisherto maximize its revenue. Our work is motivated by recent extensive studies on influence models for social networks. It has been noted that the promoted products could either be competitive or complementary such as Kindle versus Nook e-reader or Kindle cover with Kindle, respectively. Our models evaluate the revenue/cost effect of marketing those types of products through a social network, focusing on the issues of revenue maximization and complementary and competitive effects of products on each other. We take the algorithmic complexity approach for revenue maximization under those models and prove NP-hardness, non-approximability results for general structures, and polynomial time algorithms and applications for special classes of networks.
Qi Qi, Wen-Wei Wang, Ling-Fei Yu
. Competitive and Collaborative Influence in Social Networks[J]. Journal of the Operations Research Society of China, 2019
, 7(1)
: 169
-182
.
DOI: 10.1007/s40305-018-00237-6
[1] Romero, D.M., Kleinberg, J.:The directed closure process in hybrid social-information networks, with an analysis of link formation on Twitter. arXiv:1003.2469(2010)
[2] Kautz, H., Selman, B., Shah, M.:Referral web:combining social networks and collaborative filtering. Commun. ACM 40(3), 63-65(1997)
[3] La Due Lake, R., Huckfeldt, R.:Social capital, social networks, and political participation. Political Psychol. 19(3), 567-584(1998)
[4] Achrol, R.S., Kotler, P.:Marketing in the network economy. J. Mark. 63, 146-163(1999)
[5] Hagel, J.:Netgain:expanding markets through virtual communities. J. Interact. Market. 13(1), 55-65(2000)
[6] Wenger, E., McDermott, R.A., Snyder, W.:Cultivating Communities of Practice:A Guide to Managing Knowledge. Harvard Business School Press, Brighton (2002)
[7] Kimmel, A.J.:Rumors and Rumor Control:A Manager's Guide to Understanding and Combatting Rumors. Routledge, London (2013)
[8] Jansen, B.J., Zhang, M., Sobel, K., Chowdury, A.:Twitter power:Tweets as electronic word of mouth. J. Am. Soc. Inf. Sci. Technol. 60(11), 2169-2188(2009)
[9] Richardson, M., Domingos, P.:Mining knowledge-sharing sites for viral marketing. In:KDD, pp. 61-70(2002)
[10] Aspnes, J., Chang, K., Yampolskiy, A.:Inoculation strategies for victims of viruses and the sum-ofsquares partition problem. In:ACM-SIAM Symposium on Discrete Algorithms, pp. 43-52(2005)
[11] Berger, N., Borgs, C., Chayes, J.T., Saberi, A.:On the spread of viruses on the internet. In:ACM-SIAM Symposium on Discrete Algorithms, pp. 301-310(2005)
[12] Watts, D.J., Strogatz, S.H.:Collective dynamics of ‘small-world’ networks. Nature 393, 440-442(1998)
[13] Mossel, E., Roch, S.:On the submodularity of influence in social networks. In:Symposium on Theory of Computing, pp. 128-134(2007)
[14] Kempe, D., Kleinberg, J., Tardos, E.:Influential nodes in a diffusion model for social networks. In:International Colloquium on Automata, Languages, and Programming, pp. 1127-1138(2005)
[15] Domingos, P., Richardson, M.:Mining the network value of customers. In:Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57-66. ACM, New York (2001)
[16] Kempe, D., Kleinberg, J., Tardos, E.:Maximizing the spread of influence through a social network. In:Proceedings of the 9th International Conference on Knowledge Discovery and Data Mining, pp.137-146. ACM, New York (2003)
[17] Chen, N.:On the approximability of influence in social networks. In:Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1029-1037(2008)
[18] Carnes, T., Nagarajan, C., Wild, S.M., van Zuylen, A.:Maximizing influence in a competitive social network:a follower's perspective. In:Proceedings of the 9th International Conference on Electronic Commerce ACM (2007)
[19] Bharathi, S., Kempe, D., Salek, M.:Competitive influence maximization in social networks. In:International Workshop on Web and Internet Economics. Springer, Berlin (2007)
[20] Halldórsson, M.M.:Approximations of weighted independent set and hereditary subset problems. In:Proceedings of the 5th annual international conference on Computing and combinatorics, pp. 261-270. Springer, Heidelberg (1999)
[21] Khot, S., Ponnuswami, A.K.:Better inapproximability results for maxclique, chromatic number and min-3Lin-deletion. In:Proceedings of the 33rd international conference on Automata, Languages and Programming, pp. 226-237(2006)
[22] Austrin, P., Khot, S., Safra, M.:Inapproximability of vertex cover and independent set in bounded degree graphs. In:24th Annual IEEE Conference on Computational Complexity, IEEE (2009)
