# LFR benchmark Lancichinetti, Fortunato, Radicchi (2008) が提案したコミュニティ検出アルゴリズム評価用のベンチマークグラフ生成モデル。それ以前に標準的だった Girvan-Newman ベンチマークや planted `-partition モデルは全頂点がほぼ同じ次数・全クラスタが同じサイズであり、次数分布・コミュニティサイズ分布ともに大きく不均一な実世界ネットワークと乖離していた。LFR ベンチマークは次数分布とコミュニティサイズ分布の両方をべき乗則(指数はそれぞれ τ1, τ2)にすることで、より厳しく現実的なテストを課す([[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] 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) 内部/外部エッジ比率は混合パラメータ µ で制御される。Lancichinetti and Fortunato (2009) による比較評価では、Infomap (Rosvall and Bergstrom) が最良の性能を示し、[[Vincent D. Blondel]] らの手法(Louvain 法)と Ronhovde and Nussinov の手法も良好かつほぼ線形時間で高速だった。モジュラリティ系手法(Blondel et al. を除く)は解像度限界のため µ が大きい(コミュニティ構造が弱い)領域で性能が悪化した([[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] p.81)。 ## 関連 - ソース: [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] - エンティティ: [[Girvan-Newman algorithm]] / [[Vincent D. Blondel]] / [[Rosvall-Bergstrom MDL method]] - 概念: [[モジュラリティ]]