WWW2012勉強会：Information Diffusion in Social Networks
- 1. WWW2012勉強会 ? ? Session ?18: ? Informa3on ?Di?usion ?in ?Social ?Networks 筑波大?山口祐人（D1） 12/07/22 WWW2012勉強会 1
- 2. Session ?18: ? Informa3on ?Di?usion ?and ?Social ?Media ?? Informa(on ?Transfer ?in ?Social ?Media ? –? Greg ?Ver ?Steeg, ?Aram ?Galstyan ? (University ?of ?Southern ?California) ? ?? The ?Role ?of ?Social ?Networks ?in ?Informa(on ?Di?usion ? –? Vineet ?Chaoji, ?Sayan ?Ranu, ?Rajeev ?Rastogi ?(Facebook), ? Rushi ?BhaP ?(University ?of ?Michigan) ? ?? Recommenda(ons ?to ?Boost ?Content ?Spread ?in ?Social ? Networks ? –? Eytan ?Bakshy, ?Itamar ?Rosenn ?(UCSB), ? Cameron ?Marlow, ?Lada ?Adamic ?(Yahoo! ?Labs) ? 12/07/22 WWW2012勉強会 2
- 3. Informa(on ?Transfer ?in ? Social ?Media 12/07/22 WWW2012勉強会 3
- 4. 概要 ?? 情報理論的にノード間のアクティビティの因果関係を 解明 ? –? 例）?ツイートのタイミング ? –? Informa3on ?Transfer ?(Transfer ?Entropy)を算出 ? ?? Informa3on ?Transferを用いてノードのアクティビティを 予測 ? –? 例）?AがツイートしたらBもツイートする ? ?? Model-?‐freeなアプローチ ? –? ノードのアクティビティに対する仮定が一切いらない ? 12/07/22 WWW2012勉強会 4
- 5. Informa3on ?Transfer ?? ユーザXが時刻tにツイートしたら1を取る確率変数 Xt(t!k ) = {Xt , Xt!1,..., Xt!k } ?? XからYへのInforma3on ?Transfer（Transfer ?Entropy） TX!Y = H (Yt | Yt"1 ) ) " H (Yt | Yt"1 ), Xt"1 ) ) (t"k (t"k (t"k 過去のYのアクティビティの系列が与えられた時の ? 現在のYのアクティビティのエントロピー ? ? 引く ? Xの観測によって ? ? 減った不確かさ 過去のYとXのアクティビティの系列が与えられた時の ? 現在のYのアクティビティのエントロピー ? 12/07/22 WWW2012勉強会 5
- 6. 结果① フォロワー数が同じでも ? I.T.は振れ幅が大きい ネットワークからの ? Informa(on ?Transferの ? 図は論文中より引用（Figure ?8） 算出は難しい 12/07/22 WWW2012勉強会 6
- 7. 结果② I.T.の大きいペアはほとんどが ? プロモーションアカウント 表は論文中より引用（Table ?1） 12/07/22 WWW2012勉強会 7
- 8. 结果③ I.T.の大きいペアの ? ツイートのタイミング 図は論文中より引用（Figure ?10） ツイートのタイミングを ? 予測できる ? 12/07/22 WWW2012勉強会 8
- 9. The ?Role ?of ?Social ?Networks ?in ? Informa(on ?Di?usion 12/07/22 WWW2012勉強会 9
- 10. 概要 ?? Social ?in?uence ?or ?Homophily? ? –? Homophilyの影響 ? ?? 友達同士は類似した興味を持っている ? ?? 同じ情報源を購読している可能性が高い ? –? 同じWebページを見たからといって必ずしもSocial ?in?uenceで あるとは言えない ? ?? Strong ?3e ?or ?weak ?3e? ? –? Strong ?3eで繋がっているペア程、同じWebページを見る可能性 は高いが、それはSocial ?in?uenceの影響なのか？ ? ?? 私達（Facebook）が持っているデータで検証しましょう！！ ? 12/07/22 WWW2012勉強会 10
- 11. 実験方法 ?? 以下の二つの状況を比較 ? –? Feed: ? ?? Facebookのfeed上で友人がシェアしたURLを見せる ? ?? 情報の入手源はfeedからもしくは他から ? –? No ?feed: ? ?? feed上で友人がシェアしたURLを隠す ? ?? 情報の入手源は他から ? ?? それぞれについてURLをReshareする確率を算出 ? 12/07/22 WWW2012勉強会 11
- 12. データ 2.5 ?million ?subjects ?（ユーザ） ? 0.75 ?million ?URLs ? 110 ?million ?subject-?‐URL ?pairs ? 偏りなくデータが ? 分割されている 表は論文中より引用（Table ?1） 12/07/22 WWW2012勉強会 12
- 13. 结果?ー?Exposure ?e?ects ?? Reshareの確率は7.37倍上 がった ? –? feed: ?0.191% ? –? no ?feed: ?0.025% ? ?? feedの方がすぐにreshare した（右図） ? 図は論文中より引用 ? （Figure ?3 ?(b)） 12/07/22 WWW2012勉強会 13
- 14. 结果?ー?Tie ?strength 実はweak ?3eの方がsocial ?in?uenceの影響が大きい ? ?Strong ?3eになるにつれてhomophilyの影響のほうが大きくなるため 12/07/22 WWW2012勉強会 14
- 15. Recommenda(ons ?to ?Boost ? Content ?Spread ?in ?Social ?Networks ? 12/07/22 WWW2012勉強会 15
- 16. 概要 ?? SNSでは情報拡散が重要 ? –? 新しい有益な情報が手に入る ? –? è?Content ?Maximiza3on ? ?? 既存のノード推薦手法では不十分 ? –? 共通の友人、プロファイルの類似度、etc ? –? è?Content ?Maximiza-onを考慮した推薦手法を提案 ? ?? 本研究の貢献 ? –? Problem ?de?ni3on ? –? Proposing ?Approximate ?Algorithm ? –? Conduc3ng ?Experimental ?Experiments ? 12/07/22 WWW2012勉強会 16
- 17. Content ?Maximiza3onを考慮した Recommenda3on 図は論文中より引用（Figure ?1） l?? Dに推薦する候補はEとC?（共通の友人がいるため） ? ?? どちらがより情報拡散を促進するか ? l?? Cを推薦すれば、AとBに情報が届く可能性が高まる 12/07/22 WWW2012勉強会 17
- 18. Content ?Maximiza3on ?Problem ?? 各ノードiは三つのパラメータを持つ ? –? pi: ?情報伝搬する確率 ? ?? e.g.） ?RTする確率 ? –? ci: ?生成または見つけたコンテンツ ? ?? e.g.） 発信したツイート、共有したWebページ ? –? Ni: ?自身に”似ている”ノード集合 ? ?? e.g.） 共通の友人が多いユーザ、ツイートの内容が似ているユーザ ? ?? このとき、次のようなエッジ集合X={ ?(i, ?j) ?| ?i,j∈V ?}を作る ? １． ? f (X) = ! ! PX (i, c) を最大にする ? i c PX (i, c) ：Xを追加したグラフにおいて、cがiに到達する確率 ? ２． ?i ! N j , j ! N i ? ３． ?あるノードに対して推薦するエッジは最大k個 12/07/22 WWW2012勉強会 18
- 19. 実験 ?? Datasets ? –? Wikipedia, ?TwiPer, ?Flickr, ?Epinion ? ?? Methods ? –? Greedy ? ?? f(X)が最も増加するエッジを１つずつ加えていく ? –? Con3nuous ?Greedy ?(CG) ?– ?提案手法 ? ?? 全てのエッジについてXに入る確率を与える ? –? Degree ? ?? 次数の大きいノード間にエッジを張る ? –? Friend-?‐of-?‐Friend ?(FoF) ? ?? 共通の友人が多いノード間にエッジを張る 12/07/22 WWW2012勉強会 19
- 20. 结果 図は論文中より引用（Figure ?8） 12/07/22 WWW2012勉強会 20