
Competitive Diffusion on Weighted GraphsCompetitive Diffusion on Weighted Graphs 
"/Ito, Takehiro/"Ito, Takehiro ,
"/Otachi, Yota/"Otachi, Yota ,
"/Saitoh, Toshiki/"Saitoh, Toshiki ,
"/Satoh, Hisayuki/"Satoh, Hisayuki ,
"/Suzuki, Akira/"Suzuki, Akira ,
"/Uchizawa, Kei/"Uchizawa, Kei ,
"/Uehara, Ryuhei/"Uehara, Ryuhei ,
"/Yamanaka, Katsuhisa/"Yamanaka, Katsuhisa ,
"/Zhou, Xiao/"Zhou, Xiao
9214pp.422

433 , 20150805 , Springer
ISSN:03029743
ISBN:9783319218397
Description
Consider an undirected and vertexweighted graph modelinga 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 NPhard even for seriesparallel graphs with positive integer weights, and is NPhard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudopolynomial 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.
Algorithms and Data Structures, 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 57, 2015. Proceedings
FullText
https://dspace.jaist.ac.jp/dspace/bitstream/10119/13758/1/21473.pdf