|
|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/13758
|
| タイトル: | Competitive Diffusion on Weighted Graphs |
| 著者: | Ito, Takehiro
Otachi, Yota
Saitoh, Toshiki
Satoh, Hisayuki
Suzuki, Akira
Uchizawa, Kei
Uehara, Ryuhei
Yamanaka, Katsuhisa
Zhou, Xiao |
| キーワード: | competitive diffusion
graph class
social network
NP-completeness
game theory |
| 発行日: | 2015-08-05 |
| 出版者: | Springer |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 9214 |
| 開始ページ: | 422 |
| 終了ページ: | 433 |
| DOI: | 10.1007/978-3-319-21840-3_35 |
| 抄録: | Consider an undirected and vertex-weighted 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 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. |
| Rights: | This is the author-created version of Springer, Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka and Xiao Zhou, Lecture Notes in Computer Science, 9214, 2015, 422-433. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-319-21840-3_35 |
| URI: | http://hdl.handle.net/10119/13758 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 21473.pdf | | 318Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
