Word of Mouth: Rumor Dissemination in Social Networks - todo314 @ ウィキ

Word of Mouth: Rumor Dissemination in Social Networks

• Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer
• SIROCCO 2008

概要

• Bharathi+WINE'07とかあるけど，先手に注目したらしい？
• 先手がどうやっても負けるインスタンスがある
• Centroid problem
  • 先手: 後手が選ぶ頂点数が分かった上で最適なシード集合を選択する
• Medianoid problem
  • 後手: 先手が選んだ頂点数がわかった上で最適なシード集合を選択する
• CentroidもMedianoidもNP-hard
• ヒューリスティクスはあまりイカないらしい

まとめ

• 難しいのでググって出てきたスライドを見た

SIROCCO 影響最大化 情報拡散

2014-04-29 22:36:29 (Tue)