Danon+ (2006) - kwakita’s diary

去年の11月に発表された Danon らの論文です。われわれの研究と非常に似た手法を提案しています。ほとんど同じといってよいでしょう(汗)。

Danon, Diaz-Guilera, and Arenas, "The effect of size heterogeneity on community identification in complex networks," Journal of Statistical mechanics. (November, 2006) P11010.

問題点	提案	評価
NGの方法*1では、少しでも大きいクラスタが優先的に成長を続けるため、モジュール性(Q値)を劣化させる	モジュール性の向上だけではなく、クラスタの大きさを加味した指標(ΔQ/a_i)を用いて最適化を行う	人工的に作成したグラフ, Zacharyの空手クラブ, Jazzバンド2, E-mail3, PGP 4, arXiv 5, WWW6, Actor7を用いて、Extreme Optimization8, CNM9とQ値に関して比較

Danonらは、最適化の指標としてNewmanらが定めた $\normalsize \Delta Q_{ij}$ の代わりに、それを隣接ノード数について、正規化したものを利用することを提案しています：
$\normalsize \Delta Q_{ij}' = \Delta Q_{ij} / a_i = 2(e_{ij} - a_ia_j) / 2$
この指標のひとつの特徴は、Newmanの $\normalsize Q_{ij}$ が対照的 $\normalsize \Delta Q_{ij} = \Delta Q_{ji}$ にさだめられていたのに対して、非対称だという点です。*10

評価

空手ネットワークの解析

Q = 0.418 となり、Donetti らの Q = 0.412 を上回っています。ちなみに、われわれの NE か小数点以下第4桁を四捨五入すると Q = 0.419 とさらによい成績を示します。あちこちのアルゴリズムを空手ネットワークに適用し、そのQとDendrogramを集めたアーカイブを用意するとよさそうですね。そのうち、われわれのNE, HE, HE0についての情報を提供しようと思います。ところで、dendrogramを図示するためのツールをご存知の方は情報をいただけませんか？

同一サイズのクラスタ群の発見

いくつかの群の間にNewmanらの方法によって確率的に辺を張り、それをCNMと改良アルゴリズムで発見する実験。Q値の高さとmutual information measureを比較している。実験においては、

大きさが一定の4群を対象とする: CNMとDanonはほぼ同じ傾向を示します。面白いと思ったのは、この場合、理想のクラスタリングはあらかじめ把握できており、そのQ値を正確に計算できます。論文は4群の場合に $\normalsize Q=3/4 - z_o/k$ が示されていました。*11
( $\normalsize 128\times1, 32\times4, 8\times16$ の計21群)を対象とする：リンク生成の確率を変化させたパラメタスウィープの全領域においてDanonはCNM以上の性能を示し、特にクラスタ間のエッジ数が多い場合のmutual information measureが25%向上できることが示されています。つまり、クラスタ間の参照が多く、クラスタリング構造がぼんやりしたときに、優秀な結果を得られることを示しているのだと思います。

実社会ネットワークの解析

ネットワーク	規模	Q_EO	Newman+	Danon+
空手	34	0.4188	0.381 (0.910)	0.4087 (0.976, +7%)
Jazz	198	0.4452	0.4389 (0.986)	0.4409 (0.990, +0.5%)
E-mail	1,144	0.5738	0.4796 (0.836)	0.5569 (0.836, +16%)
PGP	10,680	0.8459	0.7329 (0.866)	0.7462 (0.882, +1.8%)
arXiv	44,337	---	0.7165	0.7606 (+6.1%)
WWW	325,729	---	0.9269	0.9403 (+1.4%)
Actor	374,511	---	0.6829	0.7194 (+1.1%)

空手 (Zachary, '77): 空手のサークルにおける友人関係
Jazz (Gleiser & Danon): Jazzの共演関係
E-mail (Guimera+, 03): Rovirai Virgili大学におけるメール送受信関係
PGP (Guardiola+, '02): (かなり脇田の想像)PGPを使ったシステムで、知人のfingerprintを相互に証明する仕組みがあります。PGPの相互承認関係のネットワークを解析した結果ではないかと想像しています。
arXiv (Newman, '01): arXivはわたしのブログのなかで多くの文献の参照先に指定している巨大な論文アーカイブシステムです。ここでの共著関係を解析しています。
WWW (Albert & Barabasi, '99): nd.edu (University of Notre Dam) ドメインに含まれるウェブページをクロールした結果を分析しています。この場合、ネットワークは有向グラフになるはずなんですが、どうやって扱っているんだろう？
Actor (Barabasi & Albert '99): なんだろ？もしかして、ハリウッド俳優の共演関係？37万というのは大きすぎるか？

上の表で、EOとは[Duch & Arenas, '05]で提案されたアルゴリズムの結果です。三つのアルゴリズムのそれぞれについて得られたQ値を示しています。EOの計算複雑性は $\normalsize n^2\log n$ で、適用可能な範囲は10,000ノード程度が限度のようです。論文には示されていませんでしたが、Newman+とDanon+についてはEOと比較したQの比、Danon+については、Newmanと比較した場合の改善度合いをいれました。CNMに比較して、Danonの結果が優位であることは明らかなのですが、E-mailについては極めて高い優秀な結果を得ている点が面白いです。論文の流れから、クラスタの大きさのばらつきが大きい場合だとすれば美しいのですが、詳しい情報は述べられていません。空手は規模が小さいのでなんともいえませんが、arXivのようにかなり規模の大きな例については6%もの優位性を示しています。もう少し、詳しいデータが見たいのですが、各論文を個別にあたれということかな？

このようなベンチマークは重要ですので、リポジトリを用意したいですね。ほかのデータの在処も探したいですが、すでにご存知の方は教えていただけませんか。わかった情報は随時このプログに掲載していきます。

*1:Newman and Girvan, "Finding and evaluating community structure in networks," Physical Review E 69, 026113 (2004).

*2:Gleiser and Danon, "Community Structure in Jazz," Advances in Complex Systems, Vol. 6, No. 4 (2003) 565-573

*3:Arenas+, "Self-similar community structure in organisations," Physical Review E 68, 065103 (2003).

*4:Guardiola+, "Macro- and micro-structure of trust networks," Physical Review E 68, 065103 (2003).

*5:Newman, "Who is the best connected scientist? A study of scientific coauthorship networks," Physical Review E 64 (2001) 016131; Physical Review E 64 (2001) 016132.

*6:Albert, Jeong, Barabasi, "The diameter of the world wide web," Nature 401, 130-131 (1999).

*7:Barabasi and Albert, "Emergence of Scaling in Random Networks," Science, 286, 509.

*8:Duch and Arenas, "Community detection in complex networks using Extremal Optimization," hysical Review E, vol. 72, 027104, (2005).

*9:Clauset+, "Finding community structure in very large networks," Physical Review E 70, 066111 (2004).

*10:考察1: $\normalsize \Delta Q_{ij}' = \Delta Q_{ij} / (a_i + a_j)$ とでもしておけば、簡単に対照的にできる。考察2: $\normalsize a_{i}^2$ とかでなく、 $\normalsize a_{i}$ で正規化する理論的な裏付けはあったっけ？

*11:これは簡単に一般化できて、群の数が $\normalsize n$ の場合は $\normalsize Q=1 - 1/n - z_o/k$ となります。クラスタの大きさが逆羃分布になっているときの結果も計算できないかな？