The Role of Infomation Diffusion in the Evolution of Social Networks (SIGKDD 2013) #データマイニング

Lilian Weng et al.

KDD2013読み会用の発表資料です

1. Introduction

オンラインソーシャルネットワークにおけるユーザの行動はますます拡大している．
それらのシステムでは，写真・ビデオ・考え・意見などを，世界中の人々とシステム上のつながりを通してやりとりしている．
このようなやりとりによってこれまでには考えられない様な量の社会性を観察するためのデータが生み出されており，
人間のコミュニケーションメカニズムを明らかにするための量的研究が近年盛んに行われている．

social media研究の中心になっているテーマは２つで「コミュニケーション」と「社会ネットワーク自身の性質」である．
多くのネットワークモデルはシステムの構造的な成長(the dynamics of the network)か，
もしくは情報拡散の過程(the dynamics on the network)に焦点を当てたものである．
本研究は2つのdynamicsのフィードバックループを確立するものである．

social networkの進化をモデリングする研究は数多くあるが，
「どのようにリンクが作られるか」をモデリングするものの中にtradic closureというモデルがある．
これはネットワーク上の共通の友人をベースにしたモデルで単純だが強力な原理である．
=> ある2人が共通の友人を持つときに，ランダムな2人と比較してリンクを作り易い
有向グラフと無向グラフ双方に適用可能で，いくつかのネットワーク成長モデルにも組み込まれている
=>しかしそれらのモデルにはユーザの行動や，どのように情報が拡散するかについては考慮されていない

Twitterなどのようなmicro-bloggingネットワークは情報の共有に主眼を置いて設計されている.
図1にあるようにネットワークの構造によってコミュニケーションのパターンが決まる.
そしてネットワークの情報の拡散もエージェントがどのように振る舞うか,
究極的にはネットワークがどのように成長するかに影響を受ける.
本論文ではではネットワーク構造の進化の形の中における情報拡散の役割と,
social linkの形成に寄る影響がもたらすそれぞれの戦略について研究している.

本論文の貢献

情報拡散がネットワークの進化に対してシステム全体とそれぞれのレベルにおいて影響を与えるという明確なエビデンスを示した
特に情報拡散をベースに新しいリンクのかなりの部分がshortcutsであることを明らかにした(?)(chap 4.)
- ユーザが自身が読んだコンテンツを生み出した人とリンクを形成する傾向にあることを明らかにした. (4.1)
- コネクションを拡大する戦略は全てのユーザに同じものが適用できない(4.2)
  - ex: リンクを多く集めるユーザは,traffic(?)に注意を払う傾向がある
- shortcutsはprobableと同義ではなく,ユーザはコンテンツの最もアクティブなソースをフォローする傾向にあるため,トポロジカルなメカニズムだけではそれらのshortcutsの説明をすることができない.(4.3)
- traffic-based shortcutsはsocial networksを情報拡散の観点からより効率的にすることができる.(4.4)
異なるリンク形成戦略におけるシステム全体ヘの影響度(prevalence)を最尤推定する(chap 5)
リンク形成の振る舞いからユーザの分類を提案する(chap 6.)

=> 情報拡散がネットワークの進化における重要な要素であることを示した.

2. Background

communication dynamicsに関する研究の初期のモデルは伝染病の研究にインスパイアされていた.
=> 情報は人から他人へ直接のコンタクトを通じて伝わっていくという仮定

そしてそのモデルは以下の様な研究に拡張されている
- カスケード現象[26]
- 新しい情報が拡散するスピードへ影響する機能[43]
- つながり方の不均質性[49]
- クラスタリング[47]
- ユーザが生み出すコンテンツ[6]
- つながり方のパターン[44, 11, 12, 51]

別の考え方はthreshold model[29, 45]
=> ある情報について一定数の他人とコミュニケーションをとったとき、人ははその情報を拡散させることができる.
=> ユーモア,規範,振る舞い等の情報拡散と関係があると考えられている
=> Competition amoung memes in a world with limited attention[64] (拡張の例として紹介されているけど別分野すぎてよくわからない…ミーム…）

これらの研究においてはネットワークの進化は情報の拡散に比べて非常にゆっくりであるという仮定のもとで
ソーシャルネットワークの特性にstaticまたはannealedがあると考えられている.
=> annealedは鋳造するみたいな意味なので、多分ほとんど変わらないみたいな感じ

近年の研究ではその2つのタイムスケールは比較可能な形にモデリング可能だと主張されている.
2つのタイムスケールは独立という考え方[53, 50]と組み合わさっているという考え方[61, 57]があり後者は本研究と類似している考え方である.
しかしそれらのモデルは伝染病を中心に考えられているので,それぞれのノードの状態を下げるためにリンクを消したり,繋ぎ直したりすることに焦点が当てられている.
本研究で考慮されているソーシャルシステムは全く異なるメカニズムによって統治されている.

ネットワークトポロジーの成長や進化を再現しようというモデルの研究は伝統的にリンクが作られるメカニズムを定義することに焦点が当てられている.

最初に提唱したのは1959年のErdonとRenyi[22]でありその後様々な研究者によって多くの特性が明らかにされてきた.
- small-world ohenomenon[63, 39, 34, 54]
- large clistering coefficient[63, 39, 34, 54]
- temporal dynamics[51, 53]
- informaiton propagation[8]
- heterogeneos distribution in conectivity patterns[7, 33, 37, 35, 20, 23]
-- preferential attachment[7]
-- copy model[37]

preferential attanchmentをsocial contextで考えると，人々はコネクションを多く持つ人間とリンクを形成しやすいということである．
これは重要な指標ではあるけれども，social networkを再生成するための指標としては十分ではない．
そのギャップを埋める他のモデルとしてhomophiry, triadic closureがある．

Homophiryは人々は同じ似たfeatureをシェアするユーザと繋がる傾向があるという考え方．
このリンク形成に関する考え方は大規模なオンラインソーシャルネットワークにおいて近年議論されている．

Tradic closureは共通の友人を持つ個人はリンクを形成しやすいという直感に基づくモデルである．
この傾向は有向グラフと無向グラフ双方で観察されており，いくらかのネットワーク成長モデルにも組み込まれている．
最尤推定分析においてTradic closureは最も有効で指標であるとされた．

あるネットワークのスナップショットから近い未来に形成されるリンクを予測するリンク予測はネットワークの進化をモデリングする際の一要素とそうて扱われている．
リンク予測のタスクは、分類またはランキングタスクとしてみなされており，
- ノード間の類似性
- ネットワークの階層構造
- ランダムウォーク
- グラフィカルモデル
- ユーザプロフィール
などを用いて行われる．

本研究のアプローチはここまで紹介してきたものとは異なる．
リンク予測やルールに基づいた行動シミュレーションなどは行わない．
Leskovakらが行った最尤推定による手法を拡張して行う．
tradic closureをユーザ行動に拡張する

3 Meme Dataset

Yahoo Meme
- Twitterのようなマイクロブログサービス
- 2009年から2012年まで運用されていた
- 2009年4月から2010年3月までの全てのメッセージの拡散とリンク形成イベントを記録している
- jがiをフォローすると，有向グラフとしてはl = (i, j)のエッジが生まれ，jはiの投稿を受け取ることができる
- in-degree: iにフォローされているユーザの数
- out-degree: iのフォロワーの数
- ユーザは受け取ったメッセージをフォロワーに向けてリポストすることができる
- リンクの重みはjに見られた・もしくはリポストされたiによるメッセージの数で決まる
- 128,199 user, 3l485,361 edge

4. Link Creation Mechanisms

ユーザはリポストを受け取ったとき，そのメッセージの経路における2step前のユーザ(G, grandparent)とそのポストを行ったユーザ(O, origin)を知ることができる．
=> これらのユーザをフォローすることをshortcutsと呼ぶ
Triadic closureはユーザがTriadic node(△)をフォローしたときに発生する

フォローのうち84.8%はtriadic closureによるものであった
21.5%はgrandparentへのshortcuts, 19.5%はoriginへのshortscuts

フォローしてないユーザからのリポストも許容するため全てのgrandparentはtriadic nodeではない
ただそれは0.3%程度であり，triadic closureとtraffic-based shortcutsはかなり重複している．
これはinformation cascadeが浅く[5]，triadic closureとtrafic shortcutが同時に起こることを示している．

これらの結果はtriadic closureの重要な要素としてshortcutsがあることを示しており，
新しいリンクの形成においては，そのユーザからどういう情報を受け取ったかが寄与することを示唆している．