# Community detection in graphs - Chapter XVIII: Outlook > 前: [[@2010__PhysRep__Community detection in graphs - Chapter XVII Applications on real-world networks]] | 次: [[@2010__PhysRep__Community detection in graphs - Appendix A Elements of Graph Theory]] | 全体: [[Community detection in graphs]] ## 要約 本章はサーベイ全体を総括する結びの章である。著者は、グラフクラスタリング研究が「理論的な方向性なしに、かなり混沌として」成長してきたと診断し(p.90)、分野が今後取り組むべき未解決課題を列挙する。論点は、クラスタリングの目的を定める理論的枠組みの不在、信頼できるベンチマークグラフ群の未整備、階層構造をどう扱うかという設計論点、null model の精密な定義の欠如、そしてドメイン固有手法・非構造情報の統合・非古典的グラフへの拡張という将来の方向性にまたがる。 ## 主要概念 - **理論的枠組みの不在**: 「クラスタリングアルゴリズムが何をすべきかを厳密に定義する理論的枠組み」が分野に最も欠けており、コミュニティの定義自体に合意がないため、手法間の優劣を客観的に決められない (p.90)。 - **信頼できるベンチマークグラフ群**: 著者は、分野が最優先で解決すべき課題は信頼できるベンチマークグラフ群の策定であると主張する。これは単なるテストの問題を超え、コミュニティ・分割の基礎概念についての合意を要求する (p.90)。planted `\ell`-partition model(Condon and Karp, 2001)が既存ベンチマーク(Girvan–Newman ベンチマークを含む)の基盤にあるが、Lancichinetti, A. and Fortunato, S. (2009) による LFR ベンチマーク(次数・コミュニティサイズの不均一性を組み込んだ新世代ベンチマーク)と、Sawardecker, E.N. et al. (2009) による代替ベンチマークが、この方向の重要な前進として評価される (p.90)。 - **階層構造(hierarchical structure)**: 分割の「質」の評価は modularity 概念の導入以降、分野の発展の大きな部分を占めてきたが、実グラフの多くは階層構造を持ち複数の意味のある分割(階層レベル)が並立するため、単一の最良分割という発想自体が問題含みだと論じる。Clauset, A. et al. (2007, 2008) の階層的ランダムグラフ(hierarchical random graphs、第XII.B節既出)が、この論点を間接的に提起していると位置づけられる。「良い」クラスタリング手法は、グラフにコミュニティ構造があるか否か、あるとすれば階層的か単一レベルかを判定できるべきであり、階層概念は将来の手法の鍵になると著者は予想する (p.90)。 - **null model(ヌルモデル)**: コミュニティ構造を持たないグラフの精密な定義がまだ存在しないことを重要な未解決課題として指摘し、modularity の null model(configuration model による次数保存ランダム化)はその一例に過ぎないと論じる (p.90-91)。 - **ドメイン固有クラスタリング手法**: 汎用手法よりも、対象グラフの分野固有の性質を利用したドメイン固有アルゴリズムの設計が有望な方向づけとして挙げられる。Palla, G. et al. (2005) の Clique Percolation Method が、特定の社会ネットワークで clique が多いという性質に依存する例として、ドメイン固有性の限界を示す事例として再言及される (p.91)。 - **符号付きネットワーク(正負重み)**: 相関データ等、attractive/repulsive interaction を持つグラフへの拡張課題。クラスタ内は正の重み・クラスタ間は負の重みという理想分割を目指す設計が必要になる (p.91)。 ## 主要主張 - 分野は理論的な方向性なしに混沌として成長してきた、という総括 (p.90)。 - 分野に最も欠けているのは、クラスタリングアルゴリズムが満たすべき条件を厳密に定める理論的枠組みである。「What the field lacks the most is a theoretical framework that defines precisely what clustering algorithms are supposed to do.」(p.90) - 分野が最優先で解決すべき課題は信頼できるベンチマークグラフ群の策定である。「we believe that the first and foremost task that the scientific community working on graph clustering has to solve in the future is defining a set of reliable benchmark graphs」(p.90) - 現状、多数のアルゴリズムのうちどれを使うべきか科学コミュニティは判断できておらず、modularity 最適化が最も普及しているが大規模グラフでの信頼性には疑問符が付く(第VI.C節既出の指摘の再確認)。「Waiting for future reliable benchmarks, ... there are at the moment hardly solid reasons to prefer an algorithm to another」(p.91) - 「万能な」手法を追い求めることは無意味である。「there is no such thing as the perfect method, so it is pointless to look for it.」(p.91) - 実践的含意として、新規手法を提案する際は単一のベンチマークでの好成績を過信せず、複数の質の異なるベンチマーク(LFR 等)や実データでの検証を行うべきである (p.90)。 - 将来展望として、(1) 汎用手法よりもグラフの種類ごとに特化したドメイン固有手法の開発、(2) 構造情報と非構造情報(属性データ等)の統合、(3) 有向・重み付き・二部・符号付き(正負混合重み)グラフへの対応拡張、の3点を挙げる (p.91)。 ## 関連 - 全体: [[Community detection in graphs]] - 前章: [[@2010__PhysRep__Community detection in graphs - Chapter XVII Applications on real-world networks]] - 次: [[@2010__PhysRep__Community detection in graphs - Appendix A Elements of Graph Theory]] - 参照節: [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]](階層的ランダムグラフ、第XII.B節)、[[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]](ベンチマーク)、[[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]](modularity と null model)、[[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]](Clique Percolation Method) - 概念: [[モジュラリティ]]、[[コミュニティ検出]]