Competitive diffusion on weighted graphs

DOI10.1007/978-3-319-21840-3_35zbMATH Open1451.91029arXiv1412.3334OpenAlexW2408175436MaRDI QIDQ3449840FDOQ3449840

Authors: Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou 

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. 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 forest 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 for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time.

Full work available at URL: https://arxiv.org/abs/1412.3334

Recommendations

• Complexity of equilibrium in competitive diffusion games on social networks
• Multi-player diffusion games on graph classes
• The competitive diffusion game in classes of graphs
• Two-player competitive diffusion game: graph classes and the existence of a Nash equilibrium
• Multi-Player Diffusion Games on Graph Classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• Parametrized complexity theory.
• Automata, Languages and Programming
• Nash equilibria for competitive information diffusion on trees
• Complexity of equilibrium in competitive diffusion games on social networks
• Title not available (Why is that?)
• Nash Equilibria in Voronoi Games on Graphs
• A comment on pure-strategy Nash equilibria in competitive diffusion games
• A note on competitive diffusion through social networks
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Maximizing influence in competitive environments: a game-theoretic approach
• Voronoi Games on Cycle Graphs
• The Voronoi game on graphs and its complexity
• Social networks with competing products
• Scale free properties of random \(k\)-trees
• Competitive contagion in networks
• Price of Anarchy for the N-Player Competitive Cascade Game with Submodular Activation Functions
• Multi-Player Diffusion Games on Graph Classes
• Strategyproof mechanisms for competitive influence in networks

Cited In (6)

• Finding safe strategies for competitive diffusion on trees
• Multi-Player Diffusion Games on Graph Classes
• Two-player competitive diffusion game: graph classes and the existence of a Nash equilibrium
• The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality
• Existence of pure Nash equilibria in 2-player information diffusion games with strict public preferences
• ChoiceGAPs: competitive diffusion as a massive multi-player game in social networks

This page was built for publication: Competitive diffusion on weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449840)