Minimizing the expected complete influence time of a social network - todo314 @ ウィキ

Minimizing the expected complete influence time of a social network

• Yaodong Ni, Lei Xie, Zhi-Qiang Liu
• Information Sciences 2010

概要

• 最終的に全員が活性化する
  • MP3プレーヤーがカセットテープの上位互換，みたいに駆逐される設定
  • 時間が勝負

incremental chance model

• 無向グラフ G=(V,E,w)
• jumping: 1つ以上の活性頂点を近傍に持つ
• sleeping: 近傍は全て非活性
• 時刻tで頂点jは
• $$ p_t^j = \frac{\sum_{i \in N(j): \mathrm{active}}w_{ij}}{\sum_{i \in N(j)}w_{ij}} $$
• の確率で活性化
• 自分の周囲の活性頂点の（重み付き）割合
• τ(A): complete influence time
• E[τ(A)]が目的関数
• 各時刻・頂点に乱数を割り当てれば，拡散過程は決定的になる
  • ただし時刻は可算無限
• 単調っぽい

理論的結果

• 定理1: E[τ(A)]の単調性
• 定理2: E[τ(A)]の上界（tightではない
  • $ w_{ij}^* = \frac{\sum_{k \in N(j)}w_{kj}}{w_{ij}} $
  • として，A内の各頂点を根とする（有向）全域森を考える
  • E[τ(A)]≦(全域森の重み)

実験

• 劣モジュラかは知らんが，貪欲でやるにしても計算時間がヤバい
• ヒューリスティクスで何割か選ぶ
• 選んだ頂点についてE[τ(A)]の増加量を真面目に計算
• 基本的にヒューリスティクスの比較とか，何割を選ぶかとかの比較

まとめ

• 実験で定理2のgapは調べないのね…
• E[τ(A)]の良い計算方法か理論的にGoodな手法

Information Sciences 影響最大化 情報拡散

2015/04/01 21:01