« ちょっとした覚え書き：グラフの推移性とクラスタ係数はどうちがうか | メイン | 軽井沢駅前の喫茶店の店員さんに渡されたパズルを解く (ためのRパッケージを作った) »
2019年11月15日 (金)
ふつうのデータ分析のなかで個体のクラスタリングをやるように、ネットワーク・データの分析の際にもノードのクラスタリングをやりたくなることがある。この分野ではクラスタじゃなくてコミュニティと呼ぶことが多いと思うけど。
個体のクラスタリングと同様、コミュニティ検出の方法もいろいろありすぎて、私のような素人は困惑してしまうのだが、中にはやたら時間とメモリを食う奴もあれば、逆に法外に早くできちゃう奴もある。時間がかかる分にはあきらめがつくが、あまりにパッと答えが出ちゃうのは、ありがたいけどなんだか気持ち悪い...という気がする。好き勝手云ってすいません。
Clauset, A., Newman, M.E.J., Moore, C. (2004) Findng community structure in very large networks. arXiv:cond-mat/0408187v2.
というわけで、igraph の cluster_fast_greedy() のドキュメントで引用されていた資料を読んでみた。
Rのigraphパッケージには, コミュニティ検出の手法としてedge betweenness, fast greedy, label prop, leading eigen, louvain, optimal, spinglass, walktrapの8つが載っているが、このうちfast greedyというのは100万ノードくらいあるグラフであっても数分でコミュニティを返してくるので、なんだか気味が悪いのである。お前真面目にやっとんのかといいたくなる。
ノードの隣接行列を$A$とする。ノード$v$と$x$がつながっているかどうかを$A_{vw}$とする。$i=v$のときに1、そうでないときに0になる関数を$\delta(i,j)$とする。グラフのエッジ数を$m=(1/2) \sum_{vw} A_{vw}$とする。
ノード$v$が属するコミュニティを$c_v$とする。エッジのうち、両端が同じコミュニティに落ちている割合は、
$\displaystyle \frac{\sum_{vw} A_{vw} \delta(c_v, c_w)}{\sum_{vw} A_{vw}} = \frac{1}{2m} \sum_{vw}A_{vw} \delta(c_v, v_w)$
となる。この量はネットワークをうまく分割できているときに大きくなるけれど、これ自体はコミュニティ構造の指標にはなれない。すべてのノードが同じコミュニティに属していれば1になるから。
そこで、この量からランダムグラフにおけるこの量の期待値を引く。ノードの次数を$k_v = \sum_w A_{vw}$として、ランダムグラフにおいて$v$と$w$の間にノードがある確率は$k_v k_w/2m$だから、
$\displaystyle Q = \frac{1}{2m} \sum_{vw} \left( A_{vw} - \frac{k_v k_v}{2m} \right) \delta(c_v, c_w)$
これがみなさまご存知の modularity。経験的には、Qが0.3以上のときネットワークには顕著なコミュニティ構造がある。[←へー]
ネットワークのコミュニティへの分割がうまくいっているときmodularityが高いなら、modularityが高くなるような分け方を探せばいいことになる。しかし、すべての分割を通じて大域的に最大のmodularityを探すのは大変なので、なんらか近似的な最適化手法を考えたい。
というわけでですね、かつて我々はNewman(2004)でこういう手法を提案いたしました。まだコミュニティに属していないひとりきりのノードたちからはじめて、Qがもっとも大きくなるような併合を探す。これを$n-1$回繰り返すとついに全員が単一のコミュニティに入ることになる。こうして、ノードを葉としたデンドログラムができる。[←要はあれですかね、F比を評価関数にして凝集型階層クラスタリングをやるようなもんですかね]
さて、この提案の折には、隣接行列を整数の行列として持っておいて毎回行と列をマージしていけばいいや、と思っていた。しかし巨大な疎行列の場合、ほとんどの要素が0なので、この作業は無駄である。
そこで本日はもっと効率的な方法を御提案します。[←ええええ？ そういう論文なの？]
... というわけで、いちおう最後までめくったけど、論文の主旨は計算を速くするための工夫の話だったので、メモは省略。よくわからんが、ネットワークの隣接行列を更新するんじゃなくて、ネットワークのコミュニティの隣接行列を更新すればよくね？ というような話らしい。
要するに... やっていることは階層的クラスタリングなんだけど、ネットワーク・データの場合は元の距離行列が疎なので、計算をめっちゃ速くするテクニックがあります、ということらしい。ふうん。
論文：データ解析(2018-) - 読了：Clauset, Newman, Moore (2004) すごく大きなネットワークにおけるコミュニティ検出