「Minimizing the expected complete influence time of a social network」の編集履歴（バックアップ）一覧はこちら

「Minimizing the expected complete influence time of a social network」(2015/04/01 (水) 21:01:58) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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な手法

&tags()

2015/04/01 21:01