# Louvain法 ## 定義 [[モジュラリティ]] 最適化に基づく階層的コミュニティ検出のヒューリスティック手法。局所的なモジュラリティ最適化フェーズ(各ノードを隣接コミュニティへ移動する貪欲探索)と、見つかったコミュニティを新たなノードに凝集するフェーズを交互に繰り返す「パス」を反復し、モジュラリティが増加しなくなった時点で終了する([[@2008__JSTAT__Fast unfolding of communities in large networks]])。 Université catholique de Louvain 所属の [[Vincent D. Blondel]]、[[Jean-Loup Guillaume]]、[[Renaud Lambiotte]]、[[Etienne Lefebvre]] が2008年に提案した(通称の由来)。 ## 未解決の問い - 中間パス(最終パーティションより下位の階層)の分割精度は原論文では未検証([[@2008__JSTAT__Fast unfolding of communities in large networks]])。 - ノード処理順序が計算時間に与える影響を利用した高速化ヒューリスティックは体系化されているか。 ## 未編纂の観察 [実データ適用] ベルギー携帯電話網(260万顧客)に適用すると、フランス語圏とオランダ語圏でほぼ単一言語に分節化したコミュニティが検出され、10000人超のコミュニティ36個中35個で構成員の85%超が同一言語話者であった(Source: [[@2008__JSTAT__Fast unfolding of communities in large networks]])。 [スケーラビリティ] 1億1800万ノード・10億リンク超のWebグラフ(Stanford WebBase)を152分で処理でき、律速要因は計算時間ではなく主記憶のストレージ容量である(Source: [[@2008__JSTAT__Fast unfolding of communities in large networks]])。 - [ch-06サーベイでの位置づけ] Fortunato (2010) サーベイでは、Louvain法を「階層的な貪欲最適化」の代表として、モジュラリティ最適化アルゴリズム群(貪欲法・焼きなまし・極値最適化・スペクトル法・数理計画法・遺伝的アルゴリズム)の中でO(m)と最速級、10^9辺規模まで扱える手法と位置づける一方、局所近傍でのコミュニティ形成が不正確な場合があると指摘している(Source: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]])。 ## 関連 - ソース: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]]