Viral Marketing in Social Networks with Competing Products
Pages 2047 - 2056
Abstract
Consider a directed network where each node is either red (using the red product), blue (using the blue product), or uncolored (undecided). Then in each round, an uncolored node chooses red (resp. blue) with some probability proportional to the number of its red (resp. blue) out-neighbors.
What is the best strategy to maximize the expected final number of red nodes given the budget to select k red seed nodes? After proving that this problem is computationally hard, we provide a polynomial time approximation algorithm with the best possible approximation guarantee, building on the monotonicity and submodularity of the objective function and exploiting the Monte Carlo method. Furthermore, our experiments on various real-world and synthetic networks demonstrate that our proposed algorithm outperforms other algorithms.
Additionally, we investigate the convergence time of the aforementioned process both theoretically and experimentally. In particular, we prove several tight bounds on the convergence time in terms of different graph parameters, such as the number of nodes/edges, maximum out-degree and diameter, by developing novel proof techniques.
References
[1]
Réka Albert and Albert-László Barabási. 2002. Statistical mechanics of complex networks. Reviews of modern physics 74, 1 (2002), 47.
[2]
Mário S Alvim, Bernardo Amorim, Sophia Knight, Santiago Quintero, and Frank Valencia. 2023. A Formal Model for Polarization under Confirmation Bias in Social Networks. Logical Methods in Computer Science 19 (2023).
[3]
Vincenzo Auletta, Angelo Fanelli, and Diodato Ferraioli. 2019. Consensus in opinion formation processes in fully evolving environments. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 6022--6029.
[4]
Vincenzo Auletta, Diodato Ferraioli, and Gianluigi Greco. 2018. Reasoning about Consensus when Opinions Diffuse through Majority Dynamics. In IJCAI. 49--55.
[5]
Vincenzo Auletta, Diodato Ferraioli, and Gianluigi Greco. 2020. On the effectiveness of social proof recommendations in markets with multiple products. In ECAI 2020. IOS Press, 19--26.
[6]
Murray A Beauchamp. 1965. An improved index of centrality. Systems Research and Behavioral Science 10, 2 (1965), 161--163.
[7]
Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Pascal Lenzner, Malin Rau, and Daniel Schmand. 2022. Asynchronous Opinion Dynamics in Social Networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 109--117.
[8]
Shishir Bharathi, David Kempe, and Mahyar Salek. 2007. Competitive influence maximization in social networks. In Internet and Network Economics: Third International Workshop. Springer, 306--311.
[9]
Allan Borodin, Yuval Filmus, and Joel Oren. 2010. Threshold models for com- petitive influence in social networks. In Internet and Network Economics: 6th International Workshop. Springer, 539--550.
[10]
Ulrik Brandes. 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 2 (2001), 163--177.
[11]
Ulrik Brandes and Christian Pich. 2007. Centrality estimation in large networks. International Journal of Bifurcation and Chaos 17, 07 (2007), 2303--2318.
[12]
Robert Bredereck and Edith Elkind. 2017. Manipulating opinion diffusion in social networks. In IJCAI International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence (IJCAI).
[13]
Tim Carnes, Chandrashekhar Nagarajan, Stefan M Wild, and Anke van Zuylen. 2007. Maximizing influence in a competitive social network: a follower's perspective. In Proceedings of the ninth international conference on Electronic commerce. 351--360.
[14]
Carmen C Centeno, Mitre C Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L Szwarcfiter. 2011. Irreversible conversion of graphs. Theoretical Computer Science 412, 29 (2011), 3693--3700.
[15]
Ning Chen. 2009. On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics 23, 3 (2009), 1400--1415.
[16]
Wei Chen, Laks VS Lakshmanan, and Carlos Castillo. 2013. Information and influence propagation in social networks. Synthesis Lectures on Data Management 5, 4 (2013), 1--177.
[17]
Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 1029--1038.
[18]
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, and Paolo Turrini. 2020. Convergence of opinion diffusion is PSPACE-complete. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 7103--7110.
[19]
Colin Cooper, Robert Elsässer, and Tomasz Radzik. 2014. The power of two choices in distributed voting. In Automata, Languages, and Programming: 41st International Colloquium. Springer, 435--446.
[20]
Samik Datta, Anirban Majumder, and Nisheeth Shrivastava. 2010. Viral marketing for multiple products. In 2010 IEEE international conference on data mining. IEEE, 118--127.
[21]
Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press.
[22]
Eyal Even-Dar and Asaf Shapira. 2007. A note on maximizing the spread of influ- ence in social networks. In Internet and Network Economics: Third International Workshop. Springer, 281--286.
[23]
Joseph Farrell and Garth Saloner. 1986. Installed base and compatibility: Innova- tion, product preannouncements, and predation. The American economic review (1986), 940--955.
[24]
Uriel Feige. 1998. A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45, 4 (1998), 634--652.
[25]
Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer. 2013. Convergence in (social) influence networks. In Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings 27. Springer, 433--446.
[26]
Sanjeev Goyal and Michael Kearns. 2012. Competitive contagion in networks. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 759--774.
[27]
Yehuda Hassin and David Peleg. 2001. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation 171, 2 (2001), 248--268.
[28]
Richard M Karp. 2010. Reducibility among combinatorial problems. Springer.
[29]
Barbara Keller, David Peleg, and Roger Wattenhofer. 2014. How even tiny influence can have a big impact!. In Fun with Algorithms: 7th International Conference. Springer, 252--263.
[30]
David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137--146.
[31]
Andreas Krause and Carlos Guestrin. 2005. A note on the budgeted maximization of submodular functions. Citeseer.
[32]
Jérôme Kunegis. 2013. Konect: the koblenz network collection. In Proceedings of the 22nd international conference on world wide web. 1343--1350.
[33]
Hicham Lesfari, Frédéric Giroire, and Stéphane Pérennes. 2022. Biased Majority Opinion Dynamics: Exploiting graph k-domination. In IJCAI 2022-International Joint Conference on Artificial Intelligence.
[34]
Jure Leskovec and Rok Sosič. 2016. SNAP: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technolog 8, 1 (2016), 1.
[35]
Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering 30, 10 (2018), 1852--1872.
[36]
Yishi Lin and John CS Lui. 2015. Analyzing competitive influence maximization problems with partial information: An approximation algorithmic framework. Performance Evaluation 91 (2015), 187--204.
[37]
Weiyi Liu, Kun Yue, Hong Wu, Jin Li, Donghua Liu, and Duanping Tang. 2016. Containment of competitive influence spread in social networks. Knowledge-Based Systems 109 (2016), 266--275.
[38]
Wei Lu, Wei Chen, and Laks VS Lakshmanan. 2015. From Competition to Com- plementarity: Comparative Influence Diffusion and Maximization. Proceedings of the VLDB Endowment 9, 2 (2015).
[39]
S Mishra, Jaikumar Radhakrishnan, and Sivaramakrishnan Sivasubramanian. 2002. On the hardness of approximating minimum monopoly problems. In FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science: 22nd Conference Kanpur, India, December 12-14, 2002 Proceedings. Springer, 277--288.
[40]
Seth A Myers and Jure Leskovec. 2012. Clash of the contagions: Cooperation and competition in information diffusion. In 2012 IEEE 12th international conference on data mining. IEEE, 539--548.
[41]
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions-I. Mathematical programming 14 (1978), 265--294.
[42]
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford infolab.
[43]
Nishith Pathak, Arindam Banerjee, and Jaideep Srivastava. 2010. A generalized linear threshold model for multiple cascades. In 2010 IEEE International Conference on Data Mining. IEEE, 965--970.
[44]
Svatopluk Poljak and Daniel Turzík. 1986. On pre-periods of discrete influence systems. Discrete Applied Mathematics 13, 1 (1986), 33--39.
[45]
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 3 (2007), 036106.
[46]
Matthew Richardson and Pedro Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. 61--70.
[47]
Ryan Rossi and Nesreen Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI, 4292--4293.
[48]
Grant Schoenebeck, Biaoshuai Tao, and Fang-Yi Yu. 2020. Limitations of Greed: Influence Maximization in Undirected Networks Re-visited. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). 1224--1232.
[49]
Maxim Sviridenko. 2004. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters 32, 1 (2004), 41--43.
[50]
Liangde Tao, Lin Chen, Lei Xu, Weidong Shi, Ahmed Sunny, and Md Mahabub Uz Zaman. 2022. How Hard is Bribery in Elections with Randomly Selected Voters. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
[51]
Feng Wang, Jinhua She, Yasuhiro Ohyama, Wenjun Jiang, Geyong Min, Guojun Wang, and Min Wu. 2021. Maximizing positive influence in competitive social networks: A trust-based solution. Information sciences 546 (2021), 559--572.
[52]
Bryan Wilder and Yevgeniy Vorobeychik. 2018. Controlling Elections through Social Influence. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
[53]
Hong Wu, Weiyi Liu, Kun Yue, Weipeng Huang, and Ke Yang. 2015. Maximizing the spread of competitive influence in a social network oriented to viral marketing. In Web-Age Information Management: 16th International Conference, WAIM 2015, Qingdao, China, June 8-10, 2015. Proceedings 16. Springer, 516--519.
[54]
Abdolahad N Zehmakan. 2019. On the spread of information through graphs. Ph.D. Dissertation. ETH Zurich.
[55]
Ahad N Zehmakan. 2020. Opinion forming in Erd's-Rényi random graph and expanders. Discrete Applied Mathematics 277 (2020), 280--290.
[56]
Ahad N Zehmakan. 2021. Majority opinion diffusion in social networks: An ad- versarial approach. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5611--5619.
[57]
Ahad N Zehmakan, Xiaotian Zhou, and Zhongzhi Zhang. 2023. Viral Marketing in Social Networks with Competing Products. arXiv preprint arXiv:2312.15819 (2023).
[58]
Yuqing Zhu, Deying Li, and Zhao Zhang. 2016. Minimum cost seed set for competitive social influence. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. IEEE, 1--9.
[59]
Zhiqiang Zhuang, Kewen Wang, Junhu Wang, Heng Zhang, Zhe Wang, and Zhiguo Gong. 2020. Lifting majority to unanimity in opinion diffusion. In ECAI 2020. IOS Press, 259--266.
Index Terms
- Viral Marketing in Social Networks with Competing Products
Recommendations
Majority opinion diffusion: when tie-breaking rule matters
AbstractConsider a graph G, which represents a social network, and assume that initially each node is either blue or white (corresponding to its opinion on a certain topic). In each round, all nodes simultaneously update their color to the most frequent ...
Majority vote in social networks
AbstractConsider a graph G and suppose that initially each node is colored either black or white. In the majority model, in each round all nodes simultaneously update their color to the most frequent color among their neighbors.
Experiments on the graph ...
Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsConsider a graph G with n nodes and m edges, which represents a social network, and assume that initially each node is blue or white (indicating its opinion on a certain topic). In each round, all nodes simultaneously update their color to the most ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AAMAS '24
Sponsor:
AAMAS '24: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 31Total Downloads
- Downloads (Last 12 months)31
- Downloads (Last 6 weeks)7
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in