こんばんは、dataMKです。
今日は、ソーシャルグラフのクラスタリングについて書きたいと思います。
とはいえ、そんなに簡単にできるわけもありません。考えるためのモデルを考えてみましょう。
まずは自分を中心に考えたとき、ソーシャルグラフはどんな風に見えるでしょうか？
上記画像は、http://developer.mixi.co.jp/appli/spec/pc/get_mymixi_info/
からの抜粋です。
自分を中心に考え見ると、その周りには友人や、同僚や、家族などのつながりがあります。
それが距離1と表現されてます。また、そのつながりから次のつながりが距離2と表現されています。
この距離1と距離2のつながりだけ見ても興味深いつながりが出てくると思います。
会社のつながり、趣味のつながり、出身学校のつながり、地域のつながり、などなど。
実際のグラフはこんな感じでしょう。（http://ameblo.jp/chimu841/entry-10531891845.html から抜粋）
視覚的に見るとつながりが密と疎になっている部分が存在することがわかります。
この密になっている部分と疎になっている部分をわけるといくつかの部分グラフになります。
この部分グラフを一つのクラスタと考えるモデルで考えてみたいと思います。
以前、GephiというツールのLouvain法を利用したクラスタリング方法を紹介しましたが今回は
別のアプローチをしたいと思います。
まずは、簡単なグラフで考えてみましょう。
上記グラフを二つ分けてくださいといったら、下記のように考える人は多いのではないでしょうか？
もし幾何学的に考えたとすると、一つの案としてループになっていないつながりを切断することで
二つのクラスタに分けることができます。
これをベースに次のグラフを考えてみましょう。
ループがいくつか増えました。こうなっただけで状況は複雑になります。
ひとつ前のグラフでは独立したループが二つでしたが、今回はループの中にループが存在します。
そもそもこれ一つでグループなのではないかという意見もあるでしょう。
ここでクラスタ＝ループではなくもう少し条件を加えてみます。
クラスタは、n個のつながりを切断した時にできる非連結グラフとしてみましょう。
非連結グラフというのは、グラフA上のどの点からもグラフB上の点へつながりが
存在しない場合、AとBは非連結グラフといいます。
上記の場合、いろいろな非連結グラフを作成することができますが、対称性を考えると
３つに分けることができそうです。
アイデアとしては、いくつかのつながりを切断することで非連結グラフが増えますが、
できるだけ要素が密に結合している非連結グラフを残すように切断する仕方を探すアルゴリズムを
考えれば良さそうです。
一つの案としては、トポロジーのホモロジー計算で求めるといったことも良いでしょう。
実際に下記の切断方法は、切断方法に対してホモロジー計算で非連結グラフの数を求めるといった
アルゴリズムで求めました。
収束判定は、モジュラリティーというものを使用しました。
http://ja.wikipedia.org/wiki/%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E3%83%AA%E3%83%86%E3%82%A3
今回は、グラフ理論的なアプローチでしたがこれだけで実際のソーシャルグラフはクラスタリングできないでしょう。複雑なソーシャルグラフで適用するためのさらなる工夫が必要です。
また、この辺についても記事を書きたいと思います。