Social Networks with Competing Products

• Autorzy: Apt K.R. , Markakis E.

Identyfikatory

DOI

10.3233/FI-2014-970

• Języki publikacji: EN

Abstrakty

EN

We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all nodes adopted some product is NP-complete. In turn, we also resolve the complexity of the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s). Further, we show that the problem of computing the minimum possible spread of a product is NPhard to approximate with an approximation ratio better than W(n), in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products.

Słowa kluczowe

EN

computer science; mathematical analysis; theory of computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 3
• Strony: 225--250
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Apt K.R.

• CWI, Amsterdam, the Netherlands and University of Amsterdam, Netherlands

autor

Markakis E.

• Athens University of Economics and Business, Athens, Greece

Bibliografia

• [1] Alon, N., Feldman, M., Procaccia, A. D., Tennenholtz, M.: A note on competitive diffusion through social networks, Inf. Process. Lett., 110(6), 2010, 221–225.
• [2] Apt, K. R., Markakis, E.: Diffusion in Social Networks with Competing Products, Proc. 4th International Symposium on Algorithmic Game Theory (SAGT11), 6982, Springer, 2011.
• [3] Apt, K. R., Markakis, E., Simon, S.: Paradoxes in Social Networks with Multiple Products, Manuscript, CWI, Amsterdam, The Netherlands, 2013, Computing Research Repository (CoRR), http://arxiv.org/abs/1301.7592.
• [4] Bharathi, S., Kempe, D., Salek, M.: Competitive Influence Maximization in Social Networks, Proc. 3rd International Workshop on Internet and Network Economics (WINE), 2007.
• [5] Borodin, A., Filmus, Y., Oren, J.: ThresholdModels for Competitive Influence in Social Networks, Proc. 6th International Workshop on Internet and Network Economics (WINE 2010), 2010.
• [6] Carnes, T., Nagarajan, C., Wild, S. M., van Zuylen, A.: Maximizing Influence in a Competitive Social Network: A follower’s perspective, Proc. 9th International Conference on Electronic Commerce (ICEC), 2007.
• [7] Chamley, C. P.: Rational herds: Economic models of social learning, Cambridge University Press, 2004, ISBN 052153092X.
• [8] Chen, N.: On the Approximability of Influence in Social Networks, SIAM J. Discrete Math., 23(3), 2009, 1400–1415.
• [9] Domingos, P., Richardson, M.: Mining the Network Value of Customers, Proc. 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2001.
• [10] Easley, D., Kleinberg, J.: Networks, Crowds, and Markets, Cambridge University Press, 2010.
• [11] Goldenberg, J., Libai, B., Muller, E.: Talk of the network: A Complex Systems Look at the Underlying Process of Word-of-Mouth, Marketing Letters, 12(3), 2001, 211–223.
• [12] Golovin, D., Krause, A.: Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization, J. Artif. Intell. Res. (JAIR), 42, 2011, 427–486.
• [13] Goyal, S.: Connections: An introduction to the economics of networks, Princeton University Press, 2007, ISBN 069112650X.
• [14] Goyal, S., Kearns, M.: Competitive Contagion in Networks, Proc. Symposium on Theory of Computing (STOC), 2012.
• [15] Granovetter, M.: Threshold models of collective behavior, American Journal of Sociology, 83(6), 1978, 1420–1443.
• [16] Immorlica, N., Kleinberg, J. M., Mahdian, M., Wexler, T.: The role of compatibility in the diffusion of technologies through social networks, ACM Conference on Electronic Commerce (J. K. MacKie-Mason, D. C. Parkes, P. Resnick, Eds.), ACM, 2007, ISBN 978-1-59593-653-0.
• [17] Jackson, M.: Social and Economic Networks, Princeton University Press, Princeton, 2008.
• [18] Kempe, D., Kleinberg, J. M., Tardos, ´E.: Maximizing the spread of influence through a social network, Proc. 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2003.
• [19] Kostka, J., Oswald, Y. A., Wattenhofer, R.: Word of Mouth: Rumor Dissemination in Social Networks, SIROCCO, 2008.
• [20] Monderer, D., Shapley, L. S.: Potential Games, Games and Economic Behaviour, 14, 1996, 124–143.
• [21] Morris, S.: Contagion, The Review of Economic Studies, 67(1), 2000, 57–78.
• [22] Mossel, E., Roch, S.: On the submodularity of influence in social networks, Symposium on Theory of Computing (STOC), 2007.
• [23] Schelling, T.: Micromotives and Macrobehavior, Norton, 1978.
• [24] Simon, S., Apt, K. R.: Choosing Products in Social Networks, Proc. 8th International Workshop on Internet and Network Economics (WINE), 7695, Springer, 2012.
• [25] Simon, S., Apt, K. R.: Social Network Games, Journal of Logic and Computation, 2013, To appear.
• [26] Takehara, R., Hachimori, M., Shigeno, M.: A comment on pure-strategy Nash equilibria in competitive diffusion games, Inf. Process. Lett., 112(3), 2012, 59–60.
• [27] Tzoumas, V., Amanatidis, C., Markakis, E.: A Game-theoretic Analysis of a Competitive Diffusion Process over Social Networks, Proc. 8th InternationalWorkshop on Internet and Network Economics (WINE), 7695, Springer, 2012.
• [28] Vega-Redondo, F.: Complex Social Networks, Cambridge University Press, 2007