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があることを示しており，
新しいリンクの形成においては，そのユーザからどういう情報を受け取ったかが寄与することを示唆している．

4.1 Statistical Analysis of Shortcuts

全てのリンク形成はランダムに行われるのではないかという帰無仮説に対するテストを行う．

NG: エッジlのクリエイターが見たgrand parentの数
N: 全ユーザの数
k(l): エッジlのクリエイターのin-degreeの数

zg = (SG - EG) / σG

tradic node, originについても同様に計算する
いずれの場合もz検定において棄却できたためtradic node, grand parent, originのいずれもランダムよりもリンクが形成されやすい

4.2 User Preference

Userのindegreeごとに計算
indegreeが少ないころはtradic closureが有効に働くがリンクが一定数(k > 75)を超えるとorigin, grand parentの影響も強くなってくる

4.3 Traffic Bias

何回見られたかとういうことがフォローのされやすさに非常に寄与している
=> トポロジーだけではLink creationを説明することはできていない

4.4 Link Efficiency

w: lを得て見られた、リポストされたメッセージの数
t: lが作られた時間
T: データ・セット中の最後のアクションの時間

Origin, GrandParentからのリンクはefficiencyが高い

5. Rules of Network Evolution

5.1

5.2 Combined Strategies

6. User Behavior

6.1 User Strategy Classification

6.2 Characteriation of User Classes

Infoはライフタイムが長く，多くの人をフォローし，Friend-drivenなユーザと比較しフォロワーも多い傾向にある。さらにポストも多い

7. Conclusion

tradic closureはNetworkの成長性を考えるときの主要因であるが，
時間が経つにつれて，情報拡散から受ける影響が強くなっていく．

ユーザが情報拡散に対してよりアクティブになるにつれて
リンクは作られやすく、より情報は拡散されやすくなっていく

これまでのLink Predictionはネットワーク全体を考えていなかったが
ネットワーク全体の成長性が寄与するのはこれにより明らかなので
Link Predictionに組み込んでいきたい=> Future work