読者です 読者をやめる 読者になる 読者になる

でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

The Bursty Dynamics of the Twitter Information Network (WWW'14)を読んだ

StanfordのJure Leskovec関連の論文

The Bursty Dynamics of the Twitter Information Network

を読んだ。


ファーストではないけどウェブ系の研究のトップ会議のWWWに4本も通しててもう何が何やら・・・。

論文はここから。

PDF

概要

Twitter上でのリツイートによる情報拡散によって、フォロー関係のネットワークがどのように変化するかを分析。

フォロー関係のネットワークはあまり変化していないように思えるが、実は一ヶ月間に全体の約10%のエッジが新しく追加(フォロー)され、3%のエッジが削除(アンフォロー)されている。

この定常的な変化に加えて、リツイートによる情報拡散が起きた時にそれによって突然大幅にフォロー関係のネットワークが変化することがある。
例えば、あるユーザuのツイートがリツイートによって、uをフォローしていないユーザvまで到達したとき、vの興味がuと合致していれば新しくフォローし始める可能性が高い。

この論文ではこの現象を観測したのと同時に、それを予測するモデルを提案した。

データ

  • 2011年11月の一ヶ月間に一回以上ツイートした1300万のユーザ
  • それらのユーザの間の17億のフォローエッジ
    • その全てのエッジについて、いつ追加されたかの時刻がわかっている(!)
  • これらのユーザの全てのツイート(12億)
  • それらのツイートに対する1億のリツイート

(フォローの時刻なんてどうやって手に入れたんだ・・・)

観測したこと

  • あるユーザuのリツイートのバースト(uのツイートが多くの人にリツイートされる)によって、それを見た多くのユーザ(uをまだフォローしていないユーザ)がuをフォローし始めるRetweet-Follow burstが起こる
  • あるユーザuが攻撃的なツイートやスパム的なツイートをし始めたとき、それを見た多くのユーザ(uをフォローしているユーザ)がuをアンフォローするTweet-Unfollow burstが起こる
    • これらの二つのバーストによって、ユーザuのego-network(uと、uから距離1のユーザの集合によって構成されるサブグラフ)内におけるtweet-similarity(ツイートの内容の類似度)が大幅に増加する
    • また、ego-network内のエッジの密度が大幅に増加する

要するに言っていることは単純で、あるユーザuに興味を持ちそうだがuのツイートを見たことのないユーザが、初めて(リツイートによって)uのツイートを見たとき、uをフォローする確率が高い。またそれによって、uをフォローしているユーザの集合がより類似したユーザの集合(coherent)になる。

モデル

あるリツイートバーストが発生したとき、それによってフォローバーストが発生するかどうかを予測する

  • イデア
    • ユーザuに対してリツイートバーストが発生したとき、それによってuとのtweet-similarityが大きい多くのユーザにツイートが到達すればフォローバーストが起きやすい
  • あるユーザuに対する他のユーザのtweet-similarityの分布は対数正規分布に従う
  • あるユーザvがuをフォローする確率new-follow probability Pvu はuとvのtweet-similarityの指数関数に比例する
  • ユーザuに対してリツイートバーストが発生したとき、それによってフォローバーストが発生する確率は

{\frac{uから2-hopで到達できるユーザのうちリツイートバーストによってuのツイートを見たユーザのnew-follow\;probabilityの総和}{uから2-hopで到達できる全てのユーザのnew-follow\;probabilityの総和}}

実験

提案手法がよかった

感想

すごく読みやすいし、読んでて面白い。新しい発見が次から次へと出てきてどんどん読み進められる。だれもが欲しがるようなデータを持ってるのがずるい。フォローのタイムスタンプなんでどうやって手に入れたんだろほんと。当然だけどデータドリブンでモデルを構築しててさすが。なにかのモデルを立てる時はどうしても自分の直感が優先されてしまってデータをないがしろにして、その結果うまくいかないモデルになりがちだから気をつけないといけないと思った。データ、分析、観測、モデル、実験っていう流れがいかにも科学っぽくてカッコいい。