読んだ：Microscopic Evolution of Social Networks(KDD08)

http://www.cs.cornell.edu/~lars/kdd08.pdf

ソーシャルネットワークの成長モデル作成のための分析とモデル化，評価．

着目した事象として

・新ノード生成間隔

・ノードの寿命

・エッジ生成ギャップ

・三角形のサブグラフ≒Connected Nearest Neighbor

各々の事象を表現するモデルを構築し，対数尤度を最大化するパラメータを分析．

最終的に，これらを組み合わせた成長モデルを構築し，より現実に即したモデルであることを示す．

・使用データ

flicker.com(画像共有サイト)

del.icio.us(ブックマーク共有サイト)

Yahoo!answers(知識共有サイト)

LINKEDIN(専門家ネットワーク構築サイト)

○Preferential Attachment

横軸に次数，縦軸にエッジ生成確率をプロットすると，ほぼ直線的に右肩上がりになる．つまり，次数が高いほどエッジが張られる確率が高い．既存のBAモデルとほぼ同様の結果．

○ノードの寿命

横軸にあるノードがネットワークにJoinしてからの時間経過，縦軸に各時刻でのエッジ確率をとると，Join直後でのエッジ生成確率が飛びぬけて高く，その後はほぼ一定になる．

○ノード選択確率とノードの次数，年齢との関係

4つの確率モデル？を定義

D:ノード選択確率が次数の大きさに比例する場合： $d_t(v)^\tau$

$d_t(v)^\tau$ …時刻tでのノードvの次数

DR:ノード選択確率がPAに従う場合： $\tau*d_t(v)+(1-\tau)*1/N(t)$

$N(t)$ …時刻tでのネットワーク内のアクティブノード数

A:ノード選択確率がノードの年齢に比例する場合： $a_t(v)^\tau$

$a_t(v)=t-t(v)$ …現在の時刻からノードvがネットワークに登場した時刻を引いた値

DA:ノード選択確率が次数と年齢の積に比例する場合： $d_t(v)*a_t(v)\tau$

それぞれで $\tau$ を変化させたときに，対数尤度が最大になる $\tau$ を分析．エッジ元，エッジ先それぞれで求める

＃次数の特徴量での比較

・全体的に，リンク元の方が，リンク先よりも対数尤度が高くなる→リンク先を正確に表現する方が難しい

・リンク先ノードの選択の方がよりランダム性があるように思われる

・ネットワーク間での分析結果の傾向がほぼ同じで，バイアスが小さい

＃年齢の特徴量での比較

・ネットワーク間で分析結果が異なる（次数ではリンク元の方が，リンク先よりも対数尤度が高くなる傾向があったが，年齢ではそれが見られない）ので，バイアスが大きくなる．特に若いノードでのエッジ確率でバイアスが大きくなると考えられる

○エッジ選択の局所性

あるノードuとwにエッジが張られるとき，それ以前の段階でのノードuとwの間のホップ数をカウント（元々異なるコンポーネントにいた場合は0hopとなる．また，1hopは存在しない）

・プロットしてやると，ホップ数に対するリンク生成確率は2重指数分布に従っている

・リンクの生成は，2hopのノード間の関係でリンクする確率が高く，三角形の関係になる傾向が強い(≒CNNモデル？)

○Triangle-closing model

エッジ $(u,w)$ が張られるとき，トライアングルの頂点となるノードvのどれを選択するか．

・Random…ランダム選択

・deg…次数

・last…エッジを張られてからの時間差

・com…uとvの共通の友人数 $c(u,v)$ を確率とする

・comlast…com+last

分析の結果としては，last,com,comlastが比較的良かったが，今回はrandom選択を採用する

○ノードとエッジの到達過程

・ノードの寿命

ノードが登場してからそれ以降エッジが張られなくなる時刻までの時間 $a(u)=t_{d(u)}(u)-t_1(u)$ とその確率をプロットすると，べき分布 $p_l(a)=\lambda exp(-\lambda a)$

・エッジ生成ギャップ

ある次数dを有したユーザuに出リンクが追加されるまでの時間 $\delta_u(d)=t_{d+1}(u)-t_d(u)$ をエッジギャップとする．

プロットすると，べき分布と指数分布のcut off

$p_g(\delta(d);\alpha,\beta)\propto \delta(d)^{-\alpha}exp(-\beta*\delta(d))$ に従う

さらに，次数dを変化させたときのパラメータ $\alpha,\beta$ の変化をみると， $\alpha$ はconst， $\beta$ は線形増加．

・ノードの発生過程

時間に対するノード数をプロットすると，多項式or指数関数でfitする

○ネットワーク生成モデル

1．ノード到達（発生）関数によりノード到達を定式化 $N(t)$

2．登場したノードvの活動期間は指数分布にしたがう $p_l(a)=\lambda exp(-\lambda a)$

3．ノードvが最初にエッジを張るノードuは，Preferential Attachmentに従う

4．それ以降のエッジ確率は，エッジギャップ確率に従う $p_g(\delta|d;\alpha,\beta)\propto (1/Z)\delta^{-\alpha}exp(-\beta d \delta)$

Zは定数

5．4に基づいてエッジが張られることになった時には，vの出エッジ先集合からランダムにノードwを選び，wの出エッジ先集合からランダムにノードuを選ぶことで，エッジ $(v,u)$ を張る

6．ノードのアクティブ期間が合わるまで4-5を繰り返す

○実験

・比較…通常のPAと比較（BAモデル）

・Flickerネットワークで実験

・評価指標…出次数分布，クラスタ係数，ホップ数

○結果

・出次数分布は2つともほぼリアルと同様

・クラスタ係数，ホップ数分布は提案法でかなり一致する．PAでは一致しない

成長モデルの話．局所的なエッジ構築の部分でVazquezのCNNモデルを引き合いに出さないのはなぜだろうか…ノードの寿命みたいな観点を入れているのが興味深かった．