Wssit slide
- 1. 情報拡散モデルを利用した 超媒介者検出法 小出明弘
- 2. 研究背景 ? ソーシャルネットワーク ? ユーザが容易につながることができる ? つながりをネットワークとして表現 ? 情報拡散現象 ? あるユーザを情報源としたときの情報の伝搬 ? 誰にどのように伝わるのか ? メカニズムの解明 バイラルマーケテイング，デマ情報の抑制
- 3. 影響最大化問題 ? 情報拡散における問題 ? 出来るだけ多くのノードに 情報を伝達できるノード ? 一定数ノードの組み合わせ ? 先行研究 ? 確率モデルを利用 ? Kempe (2003), Kimura (2008)
- 4. 超媒介者 ? 情報拡散において両方を満たすノード ? 多くのノードから情報を収集 ? 多くのノードに情報を拡散 影響最大化問題で重要となりうるノード（拡散に特化） 超媒介者になりうるノード（収集＆拡散）
- 5. モチベーション ? 超媒介者の検出 ? 情報拡散における重要ノード ? 検出アプローチ ? 基本的情報拡散モデルを利用 ? 期待影響度を利用した超媒介者検出 ? 実験?評価 ? 超媒介者とそのほか指標との関係 ? ネットワークの中心性，ランキング指標
- 6. 数式の定義 フォローネットワーク ? = (?, ?) ?:全ユーザ数 ? = ?, ?, ?, … , , ? ∈ ? × ? ノード?が持つ子ノード集合 ? ? ?(?) = ? ∈ ?; (?, ?) ∈ ? ノード?が持つ親ノード集合 ? ? ?(?) = ? ∈ ?; (?, ?) ∈ ?
- 7. 情報拡散モデル ? IC(Independent Cascade) Model (Goldenberg et al., 2001)etc. ? 情報まき散らし型 ? ? 一定の確率で情報を伝達 ? ? LT(Linear Threshold) Model (Watts, 2001)etc. ? 情報受入れ型 ? ? 各ノードに重みづけされている ? 閾値を超えるとき情報が伝達 ?′
- 8. 期待影響度算出 ? 各ノードの影響度? ?; ? の算出 1st Simulate ?th Simulate IC or LT model ??? ? 1 ? ?; ? = ? ? ?1 = 4 ? ??=6 ?=1 ? 全ノードで計算し期待影響度?(?)算出 ? ? = ? ?; ? ?(?) 1 で一様 ?(?)???ノード?が情報源になる確率 |?|
- 9. 超媒介者の検出 ? ? 検出アプローチ ? あるノードを削除 ? 出，入リンクを削除 ? 部分グラフ? ? {?}を作成 ? 超媒介者算出 ? ? ? に対し期待影響度を最も下げるノード? ? = arg max ? ? ? ?(? ? {?}) ?∈? ? = arg min ?(? ? {?}) ?∈?
- 10. データセット 現実の情報拡散ネットワーク Hyperlink ? Blogのトラックバックネットワーク ? トラックバック元から先へ有向リンク ? ノード数???12,407，リンク数???53,315 ? Enron社のメール送受信ネットワーク ? 送信者から受信者へ有向リンク ? ノード数???19,603，リンク数???210,950 ※次数分布はべき則に従うネットワーク
- 11. 実験设定 1000 Simulates ? 各ノードの影響度? ?; ? の算出 ? シミュレーション回数? = 1,000 ? ICモデル：拡散確率の設定???? ?,? = ? = 1 ? ? LTモデル：リンク重みの設定???? ?,? = 1 |?(?)| ICモデル 1 LTモデル 1 ? |?(?)| 1 ? 1 ? |? ? |
- 12. 比較指標(1) ? 影響最大化問題における重要ノード ? 超媒介者との比較 ? ? ? = ?(?; ?)でランキング ? PageRankアルゴリズム ? ? ? ? = ? ??1 ? ? ? Webページの重要度を測る ? prk ? = ? ? ? (?)でランキング ?:Google行列 ? HITSアルゴリズム ? hub (?) ? = ?∈?(?) authority ??1 (?) でランキング ? authority (?) ? = ?∈?(?) hub ??1 (?) でランキング
- 13. 比較指標(2) ? 次数中心性 dec ? = |?(?) ∩ ?(?)| ? 次数が高いほど重要 ? 近接中心性 ? ネットワークの中心にあるノードは重要 ?(?, ?) ?1 →?, ?の最短パス長 clc ? = ?(?, ?) ?∈?,?≠? ? 媒介中心性 ? 多くのノード間の橋渡しになるノードは重要 ?s,t :s, ?の最短パス数 ? ?,? (?) b?c ? = ?s,t (?):?を通るs, ?の最短パス数 ?∈? ?∈? ? ?,?
- 14. 超媒介者の期待影响度への影响 blogNW enronNW IC LT IC LT ?(?) 182.62 3.26 898.0 2.82 ?(? ? {?}) 143.53 3.25 882.70 2.79 ? BloｇNW ? IC????の削除で期待影響度が78%に減少 ? LT???ほとんど減少しない(削除前から期待影響度小) ? EnronNW ? IC????の削除で期待影響度が98%に微減 ? LT???ほとんど減少しない(削除前から期待影響度小)
- 15. 超媒介者と指標の関係(blogNW,IC) 各指標で1位のノードを除いた部分グラフでの期待影響度 Proposed I(v) dec prk hub authority clc bwc 143.53 178.55 179.74 178.18 183.75 179.74 177.54 181.25 提案手法のノードが最も期待影響度を下げる 提案手法上位ノードの各指標でのランキング Proposed I(v) dec prk hub authority clc bwc 1 49 31 53 4,904 3,317 24 6 2 118 40 51 4,960 3,209 419 45 3 586 268 653 7,085 5,322 293 57 次数，Pagerank，BWCと特に関係強い
- 16. 分析結果(enronNW,IC) 各指標で1位のノードを除いた部分グラフでの期待影響度 Proposed I(v) dec prk hub authority clc bwc 882.70 895.56 889.36 885.74 891.65 889.36 885.85 888.64 各指標の期待影響度とそれほど差が見られない 提案手法上位ノードの各指標でのランキング Proposed I(v) dec prk hub authority clc bwc 1 365 7 2 37 79 18 4 2 230 3 1 9 5 6 3 3 279 1 7 5 2 1 2 ほとんどの指標と極めて関係強い
- 17. 超媒介者として検出されたノード ? BlogNW???「愛国無罪」というタイトルのブログ ? 収集期間が古く確認できず ? EnronNW???Jerey Skilling氏 ?当時のEnron社のSenior Management ?エンロン事件前後でのメール送受信データ ※SkillingのSenior Management就任後，メール急増 ? Skillingがメールの収集、拡散に関与していた可能性
- 20. まとめ ? 超媒介者検出手法の提案 ? 情報拡散における別視点の重要ノード ? ネットワークと拡散モデルを用いて算出 ? 超媒介者とネットワーク指標との関係 ? 既存影響度最大化問題，中心性など ? 超媒介者の有用性 ? 影響度を大きく減少させるノード検出 ? ネットワーク構造に依存
- 21. 今後の課題 ? 大規模ネットワークでの実験 ? Twitterのフォローネットワーク等 ? 媒介者と各指標との関係の詳細分析 ? 幾つかの指標と媒介者には関係 ? どの指標がどの程度の強さで効いているのか ? 集合問題への拡張 ? 影響最大化問題と同様，ノードペアの組み合わせ