Abstract
Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: A note on competitive diffusion through social networks. Information Processing Letters 110(6), 221–225 (2010)
Apt, K.R., Markakis, E.: Social networks with competing products. Fundamenta Informaticae 129(3), 225–250 (2014)
Bharathi, S., Kempe, D., Salek, M.: Competitive influence maximization in social networks. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 306–311. Springer, Heidelberg (2007)
Borodin, A., Braverman, M., Lucier, B., Oren, J.: Strategyproof mechanisms for competitive influence in networks. In: Proc. of the 22nd International Conference on World Wide Web, pp. 141–151 (2013)
Borodin, A., Filmus, Y., Oren, J.: Threshold models for competitive influence in social networks. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 539–550. Springer, Heidelberg (2010)
Bulteau, L., Froese, V., Talmon, N.: Multi-Player diffusion games on graph classes. In: Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation (to appear)
Clark, A., Poovendran, R.: Maximizing influence in competitive environments: a game-theoretic approach. In: Proc. of the Second International Conference on Decision and Game Theory for Security, pp. 151–162
Cooper, C., Uehara, R.: Scale Free Properties of Random \(k\)-Trees. Mathematics in Computer Science 3(4), 489–496 (2010)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57–66 (2001)
Draief, M., Heidari, H., Kearns, M.: New models for competitive contagion. In: Proc. of the 28th AAAI Conference on Artificial Intelligence, pp. 637–644 (2014)
Dürr, C., Thang, N.K.: Nash equilibria in Voronoi games on graphs. In: Proc. of the 15th Annual European Symposium on Algorithms, pp. 17–28 (2007)
Etesami, S.R., Basar, T.: Complexity of equilibrium in diffusion games on social networks. 1403.3881
Feldmann, R., Mavronicolas, M., Monien, B.: Nash equilibria for voronoi games on transitive graphs. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 280–291. Springer, Heidelberg (2009)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (2006)
Goyal, S., Heidari, H., Kearns, M.: Competitive contagion in networks. Games and Economic Behavior (to appear)
He, X., Kempe, D.: Price of anarchy for the N-player competitive cascade game with submodular activation functions. In: Proc. of the 9th International Workshop on Internet and Network Economics, pp. 232–248 (2013)
Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic Journal of Computing 14, 87–108 (2008)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer-Verlag (2004)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)
Kempe, D., Kleinberg, J.M., Tardos, É.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1127–1138. Springer, Heidelberg (2005)
Mavronicolas, M., Monien, B., Papadopoulou, V.G., Schoppmann, F.: Voronoi games on cycle graphs. In: Proc. of the 33rd International Symposium on Mathematical Foundations of Computer Science, pp. 503–514 (2008)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proc. of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61–70 (2002)
Small, L., Mason, O.: Nash Equilibria for competitive information diffusion on trees. Information Processing Letters 113(7), 217–219 (2013)
Takehara, R., Hachimori, M., Shigeno, M.: A comment on pure-strategy Nash equilibria in competitive diffusion games. Information Processing Letters 112(3), 59–60 (2012)
Teramoto, S., Demaine, E.D., Uehara, R.: The Voronoi game on graphs and its complexity. Journal of Graph Algorithms and Applications 15(4), 485–501 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Ito, T. et al. (2015). Competitive Diffusion on Weighted Graphs. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)