読んだ:A Gap in the Community-size Distribution of a Large-scale Social Networking Site

http://arxiv.org/pdf/physics/0701168.pdf:こちらから

あらまし

近年SNSは世界中の何百万人のユーザに利用されている.SNSは,インターネット上の社会であり,そこで人々は互いに交流し,友人関係を育成する.我々は全国的なSNS(現在六百万ユーザ以上)を調査した.それは,三十万人の人々と二百万リンクを有するお互いに認めた(無向)友人ネットワークである.Newmanやそのほかのコミュニティ検出手法を用いることにより,我々はわずかなコミュニティが検出されるなかで,コミュニティサイズの範囲の存在を発見した.この新たな特徴は既存の成長ネットワークモデルでは予期されていなかった.我々は近傍接続とランダムリンクというよくしられた2つの手順による単純なモデルを表現する.我々は,このモデルがそのほかの統計的特徴である次数分布のロングテール,高い推移性,,次数相関と同様にコミュニティ分布のギャップが予期できることを示す.このモデルは,多くのソーシャルネットワークで普遍である2つの過程が,他の社会と同様にSNS内の相対頻度にどれくらい働いているか推定できる.

使用データ
Mixiの友人ネットワーク
ノード数:363,819 リンク数:1,906,878

これを弱連結成分分解した後の最大連結成分
ノード数:360,802 リンク数:1,904,641

平均ノード間距離
5.53
最大ノード間距離
22

基本的な分布とその傾向
・次数分布(power-law)
クラスター係数(次数の増加で減少)
・次数相関(次数の高いノードの友達は次数が高い)
・媒介分布(power-lawに近い,次数の増加により媒介度上昇)


コミュニティ分布

Newmanコミュニティ(エッジ媒介度を利用したコミュニティ分割アルゴリズム)
モジュラリティQ= \sum^{}_{i}(e_{ii}-\sum^{}_{j}e_{ij})=\sum^{}_{i}(e_{ii}-a^2_i)
e_{ii}= コミュニティiに属するノードの総リンク数/総リンク数
e_{ij}= コミュニティiからjにはられているリンク/総リンク数
a_{ii}= コミュニティiから他のコミュニティにはられるリンク数/総リンク数

コミュニティは約3500個に分割される

コミュニティ分布をみると,サイズが20〜400のコミュニティがわずかにしか検出されない(community gap)

次数が100,30以上のノードを除いたサブグラフでも同じような結果

既存のネットワーク生成モデルでも同様の実験
・BA(次数の高いノードにリンクが張られやすい)
・WS(レギュラーグラフを確率pで張替)
・CNN(友達の友達は友達だからリンク張りやすい)

これらのネットワークにはそのようなコミュニティ構造は見られない

そこで,CNNモデルを応用したCNNRモデルを提案

CNNの拡張で,以下の方式

・確率1-uで新ノードを追加.新ノードからランダムに選ばれたノードにリンクを張る.同時に,新ノードからvの全ての近傍に対して潜在リンク(?)の集合を作る.

・確率uで,以下の2つの過程が行われる
(1)確率1-rで,ランダムに選択されたある潜在リンクをリンクに変える
(2)確率rでランダムに選ばれた任意のノードペアにリンクを張る

このモデルで評価すると実データのような構造を表現できる!



修論のネタになる可能性があるので読んでおいた.
著者が日本の方なので読みやすい.Mixiは無向NWになるので,自分が扱うNWの場合は有向NWに見られる特徴を使う必要がありそう.
面白かった.