# walktrap Latapy, M. と Pons, P. が提案したランダムウォークに基づくコミュニティ検出アルゴリズム。固定ステップ数のランダムウォークの遷移確率から頂点間距離を定義し、Ward 法による凝集型階層的クラスタリングで分割したのち、モジュラリティで最良の断面を選ぶ([[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] p.45)。 計算量は密グラフで O(n^2 d)、実グラフでは実用上 O(n^2 log n) 程度に収まる。ステップ数の選択は「十分に広く探索するが定常極限に近づきすぎない」よう非自明な調整を要する(同 p.45-46)。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — 本アルゴリズムを扱う章。 - [[モジュラリティ]] — 最良断面の選択基準として用いられる。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — Latapy and Pons による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。