#june29jp

論文を読んだので内容のメモ．訳すというよりはボクの解釈のメモです．先日のエントリ 気が向いたので研究について書く は前置きでした．

Fast unfolding of community hierarchies in large networks

アブストラクト

ソーシャル系のサービスは秩序と乱雑さを併せ持つ複雑ネットワークとして捉えられる．SNS や携帯電話のネットワーク，Web のように大規模なものにおいては，その全体構造を把握するための解析手法が求められている．

ネットワークを密に結合したノード集合であるコミュニティ(ここではクラスタと同意)に分解するアプローチは有効だ．SNS などからコミュニティを抽出することで，トピックについて知ることができる．さらに，得られたコミュニティをノードしてメタネットワークを生成すれば，ネットワークの構造を視覚的に把握できるようになるだろう．

この論文では，コミュニティの階層構造を明らかにするシンプルな手法を提案する．これは既存のどの手法よりも優れている．実際に，260万ユーザで構成されるベルギーの携帯電話ネットワークから言語のコミュニティを見つけ出し，コミュニティ間の関係を解析する．

手法の説明などはスッ飛ばす

既存の手法でコミュニティ分割して，得られたコミュニティをノードとしてネットワークを作り直して，またコミュニティ分割して… ってのを繰り返すのがこの論文で提案されている手法．

コミュニティ分割結果の例．同じ色で塗られたノードは，最初のステップで同一コミュニティに属するノード，線で囲まれたノードが，次のステップでのコミュニティを意味する．

2つのステップを繰り返すことで，コミュニティの階層構造が浮かび上がる．

Google Maps のように，ズームレベルを変化させると見えるコミュニティも変わってくる．コミュニティの中にはさらに細かいサブコミュニティが存在する．

いきなり実験結果

提案手法を用いてベルギーの携帯電話ネットワーク(過去半年間の通話記録を用いてノード間のリンクを定義)を解析し，コミュニティを抽出した．

数十のコミュニティが存在し，それらは大きく2つに分かれている．ノードの大きさは，そのコミュニティに属するユーザの数による．赤はフランス語を話す人のコミュニティで，緑はオランダ語．

続いて，2つの言語コミュニティの間の橋になっている部位を拡大して見てみる．

ここにはさらに，英語やドイツ語を話すユーザがいて，言語の壁をこえてコミュニケーションが行われている．

さて，先の赤と緑の図に戻ってもう1度よく見てみると，赤で表されるフランス語のコミュニティ間の方が，緑のオランダ語のコミュニティ間に比べて，リンクが密になっている様子が見て取れる．これは文化の違いに起因するものだろう．

以上，メモでした．最後に一言

複雑ネットワーク，コミュニティ分割，ネットワーク可視化，面白いなぁ．ソーシャル系のサービスに慣れている人なら，これがすぐに色んなサービスに適用できそうだってことに気が付きますよね．Twitter で「クラスタ」と呼ばれているものは，複雑ネットワーク的手法で可視化できる．