> 前: [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]] | 全体: [[Community detection in graphs]] # Community detection in graphs - Chapter XV: Testing Algorithms ## 要約 クラスタリング手法の性能評価という、それまで等閑視されてきた課題を扱う章である。ベンチマークグラフの系譜(planted `-partition モデルから LFR ベンチマークまで)、分割間の類似度を測る尺度群、そして Danon et al. および Lancichinetti and Fortunato による2つの代表的な比較評価の結果を整理する(p.73-81)。 > "This is a serious limit of the field. Because of that, it is still impossible to state which method (or subset of methods) is the most reliable in applications, and people rely blindly on some algorithms instead of others for reasons that have nothing to do with the actual performance of the algorithms, like. e.g. popularity (of the method or of its inventor)." (p.73-74) 分野の現状として、多くの論文は簡単なベンチマークで新手法を試すだけであり、実際の性能ではなく人気で手法が選ばれがちであるという課題認識から本章は始まる。 ## 分類軸(taxonomy) 本章は「ベンチマークグラフ」と「分割類似度の尺度」という2本の軸で性能評価という問題を分解する。 **ベンチマークグラフの系譜** - planted `-partition モデル(Condon and Karp, 2001) — n=g·l 頂点を l 群に分け、pin/pout で内部/外部リンク確率を設定する最も基本的な生成モデル。全頂点がほぼ同じ次数・全クラスタが同じサイズという点で、実世界グラフの次数分布・クラスタサイズの不均一性と乖離している(p.75-76)。 - Girvan-Newman ベンチマーク — planted `-partition の特殊ケース(l=4, g=32, n=128)。zin/zout パラメータで内部・外部次数を表し、長らく標準として使われてきたが、実際の判別限界は zout≈12 であり、当初想定された zout<8 という閾値設定は不正確だった(p.74)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch15-fig30-gn-benchmark.png]] (FIG. 30. Girvan-Newman ベンチマークの実例(zin=15, 11, 8 の3ケース)。zin=8 では4つの群がほぼ判別不能になる。) - Gaussian random partition generator(Brandes et al.) — クラスタサイズをガウス分布にした planted `-partition の改良版(p.75)。 - relaxed caveman graphs(Watts に由来) — 互いに素なクリークから出発しエッジを再配線して作る smooth variation のベンチマーク(p.76)。 - Bagrow によるべき乗則次数ベンチマーク、Arenas et al. による階層構造を埋め込んだベンチマーク、Guimerà et al. による二部グラフ用のコミュニティ内蔵モデル、Sawardecker et al. による重複コミュニティを持つ一般化モデルなど、特定の構造的特徴に焦点を当てた派生ベンチマークも並行して提案されてきた(p.76-77)。 **LFR ベンチマーク** — [[LFR benchmark]](Lancichinetti et al., 2008)は、次数分布・コミュニティサイズ分布の**両方**をべき乗則(指数 τ1, τ2)にした点で、既存ベンチマークより実世界ネットワークに近い、より厳しいテストを課す(p.75-76)。 > "A better job in this direction has been recently done by Lancichinetti et al. (LFR benchmark) (Lancichinetti et al., 2008). They assume that the distributions of degree and community size are power laws, with exponents τ1 and τ2, respectively." (p.75) ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch15-fig31-lfr-benchmark.png]] (FIG. 31. LFR ベンチマークグラフの実例(500 頂点)。次数・コミュニティサイズの双方がべき乗則に従う。) **分割類似度の尺度** 分割間の類似度を測る尺度は3系統に大別される(p.77)。 - ペア計数に基づく尺度(pair counting measures) — a11, a01, a10, a00(頂点対の分類一致・不一致の計数)に基づく Wallace 指数・Rand 指数・Mirkin 距離・Jaccard 指数など。Rand 指数は両分割で一致して分類された頂点対の割合である(p.77-78)。 - クラスタ対応付けに基づく尺度(cluster matching measures) — classification error、normalized Van Dongen metric など、最大重複を探す尺度(p.78)。 - 情報理論に基づく尺度 — 正規化相互情報量(normalized mutual information, NMI, Danon et al., 2005)が現在最もよく使われる。NMI は分割が同一なら1、独立なら期待値0を取る(p.78-79)。 > "The normalized mutual information equals 1 if the partitions are identical, whereas it has an expected value of 0 if the partitions are independent." (p.79) Meilă は分割類似度尺度の体系的レビューを行い、variation of information(H(X|Y)+H(Y|X) による尺度)を提案した。NMI より距離としての性質(距離公理を満たす、局所性を持つ)で優れているとされる(p.78-79)。 > "Meilă (Meilă, 2007) introduced the variation of information ... which has some desirable properties with respect to the normalized mutual information and other measures. In particular, it defines a metric in the space of partitions as it has the properties of distance." (p.79) このほか、Gustafsson et al. による分割の meet(交わり)とそれに基づく距離 mmoved, mdiv、時間発展するクラスタの追跡にも応用される相対重複 sij(relative overlap)が紹介される(p.79-80)。 ## 代表手法・システムの比較 **Danon et al. (2005) の比較評価** — Girvan-Newman ベンチマーク上で複数の手法を比較し、シミュレーテッドアニーリングによるモジュラリティ最大化が最良の結果を出した。ただし計算コストが高く、大規模グラフには適用できない(p.80)。使用したアルゴリズム一覧は TABLE I にまとめられている(著者・出典・記号・計算量)(p.79-80)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch15-fig32-algorithm-performance-gn.png]] (FIG. 32. Danon et al. による Girvan-Newman ベンチマーク(zout=6,7,8)上でのアルゴリズム性能比較。) **Lancichinetti and Fortunato (2009) の比較評価** — [[LFR benchmark]] 上で各手法の NMI を混合パラメータ µt に対してプロットして比較した(使用アルゴリズム一覧は TABLE II)。Infomap(Rosvall and Bergstrom, 2008。[[Rosvall-Bergstrom MDL method]]の後継にあたる情報理論的手法)が最良の性能を示し、[[Vincent D. Blondel]] ら(Louvain 法, 2008)と Ronhovde and Nussinov(2009)の手法も良好かつ高速(ほぼ線形時間)だった。モジュラリティ系手法(Blondel et al. を除く)は解像度限界のため性能が悪化した(p.80-81)。 > "the Infomap method by Rosvall and Bergstrom (Rosvall and Bergstrom, 2008) appears to be the best, but also the algorithms by Blondel et al. (Blondel et al., 2008) and by Ronhovde and Nussinov (Ronhovde and Nussinov, 2009) have a good performance." (p.81) ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch15-fig33-algorithm-performance-lfr.png]] (FIG. 33. Lancichinetti and Fortunato による LFR ベンチマーク上での各手法の NMI 対混合パラメータ µt。手法ごとに8パネルで比較。) なお、Fan et al. による重み付きベンチマークと重み付きアルゴリズムの性能評価(WEO/GN/Potts の比較, Fig. 34)も本文中で言及されるが、対応するキャプション画像は本章の抽出範囲(p.73-81)には含まれていない(次章側に含まれる可能性がある)。 実ネットワークでの検証例としては、Zachary's karate club、Lusseau のイルカネットワーク、Girvan and Newman による American college football network(12 カンファレンス)が、既知コミュニティ構造を持つベンチマークとして挙げられている(p.77-78)。 ## 傾向と未解決課題 - 分野全体として、手法の性能を体系的に比較する研究が手薄であるという問題そのものが、本章が投げたまま解決されていない課題として提示される。実応用でどの手法(群)が最も信頼できるかは依然として不明である(p.73)。 - 実ネットワークにおいて、非構造的情報(メタデータ等)に基づく「妥当な」コミュニティ分割が、構造のみに基づく検出アルゴリズムの結果と一致する保証はない、という問題も指摘されるが解決策は示されない(p.77)。 - Lancichinetti et al. による重複コミュニティ向け NMI 拡張は、非重複分割の比較では元の NMI と厳密には一致せず近似にとどまることが指摘されているが、この不整合の解消は章内で扱われない(p.78-79)。 - 実践的指針として、新手法の性能を主張する際は単一の簡単なベンチマークでなく、次数・コミュニティサイズが不均一な LFR ベンチマークのような厳しいテストで評価すべきであり(p.75-76, p.81)、大規模ネットワークへの適用を想定するなら計算量が線形〜準線形の手法(Infomap, Louvain 法, Ronhovde-Nussinov)を優先すべきとされる(p.80-81)。 ## 関連 - ハブ: [[Community detection in graphs]] - エンティティ: [[LFR benchmark]] / [[Girvan-Newman algorithm]] / [[Vincent D. Blondel]] / [[Rosvall-Bergstrom MDL method]] - 概念: [[モジュラリティ]] - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]] - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]]