Limiting the Spread of Misinformation in Social Networks - todo314 @ ウィキ

Limiting the Spread of Misinformation in Social Networks

• Ceren Budak, Divyakant Agrawal, Amr El Abbadi
• In WWW 2011

概要

• 誤情報に対する訂正情報をイイ感じに流して誤情報の伝播を減らしたい
• submodular ってからのヒューリスティクス

問題

Multi-Campaign Independent Cascade Model

• 誤情報と訂正情報はそれぞれ辺ごとに異なる確率をとる
• 同時なら訂正優先
• 一度情報を受け取ったら以後変化しない
  • 到達時間が大事

定式化

• 既に誤情報はいくらか伝わっている
  • rターンたっている
• k個訂正情報を流すノードを選ぶ
• 保護される頂点の期待個数を最大化
• 2つのケース
  • 訂正情報が必ず伝わる
  • 誤情報の確率=訂正情報の確率

で？

• NP-hard
• submodular

アルゴリズム

Greedy based

• いつもの
• 例のごとく、Monte Carloが重い

ヒューリスティクス

• degree centrality
• early infectees
  • rターン目に誤情報に感染している確率の高い頂点を優先
• largest infectees
  • 感染すると、めっちゃ影響を与える（迷惑な）頂点を優先

実験

データセット

• Facebook、だけど小さめ

結果

• まぁ、はい、という感じ

推定

• ぶっちゃけ
• 誤情報の拡散状況は完全には分からん
• 観測データだけから
• 尤度関数で与える
• supermodular
  • 個数制約最大化は難しい

WWW information diffusion

2013-10-24 01:09:16 (Thu)