×

Word of mouth: Rumor dissemination in social networks. (English) Zbl 1143.91361

Shvartsman, Alexander A. (ed.) et al., Structural information and communication complexity. 15th international colloquium, SIROCCO 2008, Villars-sur-Ollon, Switzerland, June 17–20, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69326-0/pbk). Lecture Notes in Computer Science 5058, 185-196 (2008).
Summary: In this paper we examine the diffusion of competing rumors in social networks. Two players select a disjoint subset of nodes as initiators of the rumor propagation, seeking to maximize the number of persuaded nodes. We use concepts of game theory and location theory and model the selection of starting nodes for the rumors as a strategic game. We show that computing the optimal strategy for both the first and the second player is NP-complete, even in a most restricted model. Moreover we prove that determining an approximate solution for the first player is NP-complete as well. We analyze several heuristics and show that-counter-intuitively-being the first to decide is not always an advantage, namely there exist networks where the second player can convince more nodes than the first, regardless of the first player’s decision.
For the entire collection see [Zbl 1139.68007].

MSC:

91D30 Social networks; opinion dynamics
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bharathi, S.; Kempe, D.; Salek, M.; Deng, X.; Graham, F. C., Competitive influence maximization in social networks, Internet and Network Economics, 306-311 (2007), Heidelberg: Springer, Heidelberg
[2] Breban, R., Vardavas, R., Blower, S.: Linking population-level models with growing networks: A class of epidemic models. Physical Review E 72(4) (2005)
[3] 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 (ICEC) (2007)
[4] Cheong, O., Har-Peled, S., Linial, N., Matoušek, J.: The one-round voronoi game. Discrete & Computational Geometry (2004) · Zbl 1079.91010
[5] Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the 7th international conference on Knowledge discovery and data mining (KDD) (2001)
[6] Goldenberg, J., Libai, B., Muller, E.: Using complex systems analysis to advance marketing theory development. Academy of Marketing Sc. Rev. (2001)
[7] Goldman, A.J.: Optimal center location in simple networks. Transportation Science, 212-221 (1971)
[8] Granovetter, M., Threshold models of collective behavior, American Journal of Sociology, 83, 6, 1420-1443 (1979)
[9] Hakimi, S.: Locations with Spatial Interactions: Competitive Locations and Games. Discrete Location Theory, 439-478 (1990) · Zbl 0747.90057
[10] Hansen, P., Thisse, J.-F., Wendell, R.E.: Equilibrium Analysis for Voting and Competitive Location Problems. Discrete Location Theory, 479-501 (1990) · Zbl 0726.90040
[11] Hotelling, H., Stability in Competition, Economic Journal, 39, 41-57 (1929)
[12] Leskovec, J., Adamic, L., Huberman, B.: The dynamics of viral marketing. In: Proceedings of the 7th conference on Electronic commerce (EC) (2006)
[13] 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 (KDD) (2003) · Zbl 1337.91069
[14] Kempe, D.; Kleinberg, J.; Tardos, É.; Caires, L.; Italiano, G. F.; Monteiro, L.; Palamidessi, C.; Yung, M., Influential Nodes in a Diffusion Model for Social Networks, Automata, Languages and Programming (2005), Heidelberg: Springer, Heidelberg
[15] Leskovec, J.; Singh, A.; Kleinberg, J.; Ng, W.-K.; Kitsuregawa, M.; Li, J.; Chang, K., Patterns of influence in a recommendation network, Advances in Knowledge Discovery and Data Mining (2006), Heidelberg: Springer, Heidelberg
[16] Linden, G.; Smith, B.; York, J., Amazon.com recommendations: Item-to-item collaborative filtering, IEEE Internet Computing, 7, 1, 76-80 (2003)
[17] Marder, M., Dynamics of epidemics on random networks, Physical Review E, 75, 6, 66103 (2007)
[18] Moore, C.; Newman, M. E.J., Epidemics and percolation in small-world networks, Physical Review E, 61, 5, 5678-5682 (2000)
[19] Newman, M. E.J., Spread of epidemic disease on networks, Physical Review E, 66, 1, 16128 (2002)
[20] Pastor-Satorras, R.; Vespignani, A., Epidemic dynamics and endemic states in complex networks, Physical Review E, 63, 6, 66117 (2001)
[21] Schelling, T.: Micromotives and Macrobehavior. Norton (1978)
[22] Slater, P. J., Maximin facility location, Journal of National Bureau of Standards, 79B, 107-115 (1975) · Zbl 0327.05105
[23] Stackelberg, H. V., Marktform und Gleichgewicht (1934), Heidelberg: Julius Springer, Heidelberg · Zbl 1405.91003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.