Information Diffusion and External Influence in Networks[Myers+, KDD'12]のメモ

論文

http://cs.stanford.edu/people/jure/pubs/ext-kdd12.pdf
再びJure Leskovecのチームの論文を読んだ．情報拡散(Information Diffusion)の過程が今までの研究とは少し違う感じ．
やりたいことは，情報拡散(Information Diffusion)による影響を"ネットワーク内の影響"と"ネットワーク外からの影響"に分けられるようにモデル化すること．従来の研究はネットワーク内で閉じた情報拡散の影響分析を行っているけれど，現実は，例えばTwitterユーザーはネットの記事をTwitterとは関係ない場所で見て，その記事が面白いと思ったらTwitterで情報を流すとかそういうことをしている．もし，このような現象をネットワークに閉じた世界で見ようとすると，あたかも情報が"ジャンプして"伝わっていくようなことになる．ようするに，ネットワーク内だけで情報拡散を考えるのは不十分だよねということ．

この論文では，人は2種類の影響を受けるとする．一つ目は今まで通りのネットワークを介した影響．これはhazard functionと呼ばれる確率で定義される．二つ目は外部からの影響．これはEvent Profileという確率で定義される．ここで，影響は"伝わる"とは別の意味を表している．よくある情報拡散の話では，隣接ノードから影響を受ければ，それは感染(infected)とかアクティブというけれど，ここでは影響を受けたとしてもすぐには感染しない．むしろ言葉は悪いけれど，被曝量(amount of exposures)的な意味が強い．最初，内部や外部から情報に晒され続け，蓄積された被爆量が多くなると感染する確率が高くなるという考え方．この2種類の確率を定義した後，二項分布を使って被爆量に関する確率分布 P^{(i)}_{\exp}(n;t)を定義する．

次に，被爆量xに対する感染確率 \eta(x)を定義する．これは2つのパラメータで制御され，一つは感染確率の最大値，一つはその最大値のときの被爆量を意味する．

最終的に，あるノードiがある時刻tまでに感染する確率が定義出来る．これは， P^{(i)}_{\exp}(x;t)と \eta(x)の積をn=0から\inftyまで総和する形で表される．

このモデルのもとで，現実のデータから外部からの影響Event Profileと \eta(x)の2種類のパラメータを推定する．ちなみに，内部からの影響であるhazard functionは事前に決定し，推定しない．


実験では，人工データと実データを使っている．実データの概要は以下の通り．

  • 2011年1月の完全なTwitterデータ
    • 30億ツイートから50回以上ツイートされたURLの付いたツイートに着目
    • English only
    • 結果的に，18,186個のURLを抽出．
  • ネットワーク構成
    • 18,186個のURLが付いたツイートをしたユーザのフォローリストを取得して，そこからネットワークを作成
    • ノード: 約110万．リンク: 約1億

実験結果の概要は以下の通り．

  • 人工データでは，真のパラメータを再推定出来ることを示した
  • 2011_Tucson_shootingの事件の時のツイートに関するケーススタディ
    • この事件に関するTwitterネットワークにおけるバースト(流行)時期を検出
    • 提案モデルで，この事件に関する4つのキーとなる出来事の時期をちゃんと当てることが出来ている
  • Googleトレンドを使った評価
    • Googleトレンドにクエリを投げて，これの時刻ごとのアクティビティを真の値としたときに，提案モデルのEvent Profileと単純な方法のEvent Proflie(方法は不明)がどちらが近いか比較
    • 提案モデルの方が30%くらい真の値に近い(L2ディスタンスで比較)
  • ニュースカテゴリごとの外部影響
    • カテゴリが異なるニュース記事ごと推定したパラメータを比較して考察
    • エンターテイメントと経済と健康のニュースは良く拡散する，一方で，芸術と教育と旅行はあんまり拡散しない．
    • 世界ニュースは時間に敏感．ようするに，他のトピックと比べて早く拡散確率が最大になる．
    • 政治ニュースは最も外部からの影響が強いトピック．
    • エンターテイメントは最も内部からの影響が強いトピック．
      • フォロワー数Top30のうち，22人はエンターテイナーだからという理由付けができるらしい
    • 総合して，全体の29%が外部からの影響，残り71%が内部からの影響によって，ユーザはURLをつぶやいているらしい


この研究，モデルが新しいのは確かなのだけど，外部からの影響があることを検証するためには，使用するデータが完全でないとできない．データに欠損があれば，情報がジャンプするという主張は，ただの欠損に過ぎないと言われる．この研究ではTwitterの完全なデータを使っていると言ってる(実際どうなのかは分からないけど)．本当に完全なデータを持っているならすごい強みだなと思う．羨まし〜．