Competitive and Collaborative Influence in Social Networks

doi:10.1007/s40305-018-00237-6

Abstract

Abstract: 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.

Key words: Revenue maximization, Social network, WOM, Complexity

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.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-018-00237-6

https://www.jorsc.shu.edu.cn/EN/Y2019/V7/I1/169

[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)

Competitive and Collaborative Influence in Social Networks

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Hui-Ling Zhang, Zi Xu. An Alternating Proximal Gradient Algorithm for Nonsmooth Nonconvex-Linear Minimax Problems with Coupled Linear Constraints [J]. Journal of the Operations Research Society of China, 2026, 14(2): 502-520.
[2]	Jue-You Li, Tao Xie. An Alternating Gradient Projection Algorithm with Momentum for Nonconvex-Concave Minimax Problems [J]. Journal of the Operations Research Society of China, 2026, 14(2): 632-652.
[3]	Shu-Yu Bao, Qing-Qin Nong, Su-Ning Gong. An Improved Space Semi-Streaming Algorithm for Submodular Maximization under b-Matching Constraint [J]. Journal of the Operations Research Society of China, 2026, 14(2): 671-686.
[4]	Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du. Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization [J]. Journal of the Operations Research Society of China, 2023, 11(4): 783-807.
[5]	Ru-Jun Jiang, Zhi-Shuo Zhou, Zi-Rui Zhou. Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation [J]. Journal of the Operations Research Society of China, 2022, 10(3): 471-506.
[6]	Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan. The Continuous Knapsack Problem with Capacities [J]. Journal of the Operations Research Society of China, 2021, 9(3): 713-721.
[7]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[8]	Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard. A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(1): 145-164.
[9]	Yan Li, Sheng-Long Hu, Jie Wang, Zheng-Hai Huang. An Introduction to the Computational Complexity of Matrix Multiplication [J]. Journal of the Operations Research Society of China, 2020, 8(1): 29-43.
[10]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.
[11]	Mohammad Pirhaji,Hossein Mansouri,Maryam Zangiabadi. A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2018, 6(4): 529-544.
[12]	Jian-Chao Huang, Jin-Yan Fan. Global Complexity Bound of the Inexact Levenberg–Marquardt Method [J]. Journal of the Operations Research Society of China, 2018, 6(3): 417-428.
[13]	Behrouz Kheirfam. A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(2): 301-315.
[14]	Yu-Hong Dai, Rui Diao, Kai Fu. Complexity Analysis and Algorithm Design of Pooling Problem [J]. Journal of the Operations Research Society of China, 2018, 6(2): 249-266.
[15]	Roghayeh Etemad · Behrooz Alizadeh. Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs [J]. Journal of the Operations Research Society of China, 2017, 5(3): 347-361.