Locating the Source of Diffusion in Large-Scale Network - todo314 @ ウィキ

Locating the Source of Diffusion in Large-Scale Network

• Pedro C. Pinto, Patrick Thiran, Martin Vetterli
• PRL 2012

概要

• 情報拡散の話
• 一部の頂点だけを観測して、「「発信源」」を推定する
• モデル化+実験

モデル

• 辺の時間: 正規分布
  • 負の値はごまかす
• 発信源: uniformly at randomに選択される
• 受信者: 時刻+ソース
  • 他の頂点に伝えない
• 理不尽な仮定はおかない
  • 受信者がネットワークを分離したり、最初の観測時刻だけ記録

問題設定

• 入力
  • グラフ: G=(V,E)
  • 分布: μ_e、σ_e
  • 受信者・受信時刻の集合
• 出力
• 発信源s

アプローチ

木なら？

• 受信者は葉にいる
  • あ、はい
• 発信時刻が分かる場合も分からん場合も考える

一般の場合

• 仮定
  • 発信源から受信者まで情報は最短経路を伝わる
    • ( ﾟдﾟ)ﾊｧ?
  • BFS木の上を求めてその上で木の場合のをやる

PRL information diffusion

2014-01-30 17:19:42 (Thu)