読者です 読者をやめる 読者になる 読者になる

Locating the Source of Diffusion in Large-Scale Network (PRL'12)

  • 問題
    • ネットワーク上で拡散が起こる
    • 一部の頂点のみを観測して,発信源を推定する
  • モデル
    • 最初は発信源だけが情報を持っている
    • 隣接する頂点に情報を伝えるのにかかる時間は正規分布
    • 一部の頂点はオブザーバで観測した時刻が分かる
  • 推定アルゴリズム
    • 最尤推定
    • 木かつ発信時刻が分かる場合 → 全辺の所要時間の線形変換からなる多変量正規分布
    • 木かつ発信時刻が分からない場合 → オブザーバ 1 の時刻を引けばいい
    • 木じゃないとき → 各頂点からの BFS 木だけを考える
    • 正規分布じゃないとき → 中心極限定理があるから正規分布だと思ってええやろ
  • 実験
    • 人口データ
    • コレラの実際のデータ