Competitive diffusion on weighted graphs

DOI10.1007/978-3-319-21840-3_35MaRDI QIDQ3449840zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)