Characterizing Social Cascades in Flickrを読んだメモ
SIGCOMM 2008の併設ワークショップであるWOSN 2008（http://conferences.sigcomm.org/sigcomm/2008/workshops/wosn/program.php）で発表された論文，"Characterizing Social Cascades in Flickr", M. Cha, A. Misolve, B. Adams, K. P. Gummadiを読んだメモです．この論文では，Flickr内における写真の広まり方を，疫学的な手法を用いて説明しています．論文内では，写真がどのように人に知られていくかを明らかにしていますが，対象としている広まり方は，ソーシャルネットワークを通じた広まり方限定の解析となっています．
Flickrでは，気に入った写真があると，自分のお気に入りリストにその写真を追加する事が出来ます．そこで，この論文ではまず，ある二つの写真AとBが，どのようにしてユーザのお気に入りに追加されるかについて解析しています．
写真Aをお気に入りに追加しているユーザの数と，経過日数はほぼ比例関係にありますが，写真Bではある一時期，1日目と30日目あたりで急激に上昇しています．しかしながら，それ以外の日では同じように，お気に入りに追加しているユーザ数と経過日数は，傾きは小さいですが比例関係にあります．ちなみに，最終的に，どちらの写真も（必要とした日数は違うものの）およそ1400ユーザのお気に入りに追加されたそうです．
それぞれの写真がお気に入りに追加される様子はわかったのですが，著者等はさらに，Social Cascadesという概念を用いて，別の視点からの解析を行っています．Social Cascadesとは，あるユーザが写真Aをお気に入りに追加したとき，そのユーザをコンタクトリストに持つ，別のユーザがお気に入りに追加し，それが再帰的に繰り返されるような状態をいいます．このようにしてコンテンツが広まった場合，Social Cascades経由で広まったといい，そうでない場合を，Social Cascades経由以外で広まったとしています．この論文では，写真AとBが，どの程度の割合で，Social Cascades経由でお気に入りに追加されたかを調べています．
著者等が調べた結果，写真AとBともに，Social Cascades経由でお気に入りに追加された数が，いずれの時点でも全体のおよそ半分以上をしめていたそうです．しかしながら，Social Cascades経由でお気に入りに追加された数の方が少なくなる時点がBにあり，それはSocial Cascades以外の何らかの要因（例えば外部からのリンクなど）が原因で広まったとことを示しています．
次に著者等は，Social Cascadesでの広まりの速度について調べています．ここで，例えば，以下のようなSocial Cascadesがあったとします．
A -> B -> C
これは，Aが一番始めに写真をお気に入りに追加した人（infector）で，BがA経由でお気に入りに追加した人（infectee）となり，CはB経由でお気に入りに追加した人となります．特に何の変哲もないように思えますが，実は，A -> B経由より，B -> C経由のほうが感染により時間がかかっているそうです．これは，感染が広まるにつれて，広まる速度が落ちていくウィルスのようにもみえます．
著者等が調べた結果，A -> Bとなるようなのは，Aが感染してから（お気に入りに追加してから），Bが感染するまでにかかった日数は3日（50パーセンタイル）となり，Bが感染してからCが感染するまでに必要な日数は，50日（50パーセンタイル）となったそうです．
はじめの感染者が現れたとき，次に何人が感染するかという値は，免疫学の世界ではR0や，basic reproduction number(http://en.wikipedia.org/wiki/Basic_reproductive_rate)と呼ばれており，病原菌が持つ感染力の強さをあらわす値として知られているそうです．例えばHIVではR0は2〜5，はしかでは12〜18となります．ここで，R0 < 1ならば，その病原菌はこれ以上広まらないということになり，免疫学ではR0 < 1とすることが課題となっているそうです．
実は，Scale-FreeなネットワークでR0を求める方法は既に考案されており（"Infection Dynamics on Scale-Free Networks", R. M. May and A. L. Lloyd, Pysics Review E, 2001），それは以下のようになります．
R0 = ρ0・< k^2 > / < k >^2
ここで，kはノードの次数，<・>は平均値，ρ0 = β・γ・< k >となります．ただし，βは感染率，γは感染期間となります．
この論文では，ρ0を写真をお気に入りに追加する確率（A -> Bとなるとき，Bがお気に入りに追加する確率）として，R0を推測する方法を提案しています．その結果，実測した値と推測値は，非常に近い値となることが分かったそうです（ピアソンの相関係数は0.9765）．ただし，Flickrにおける平均次数は，< k > = 14.7なので，< k^2 > /
以上が簡単な概要となります．すなわち，この論文の主張することに依ると，ノードの平均次数と，二番目にお気に入りに追加した人の割合から，そのコンテンツが将来，どのくらいの人気になるかが推測できることになります．
