# Rosvall-Bergstrom MDL method Rosvall, M. と Bergstrom, C. T. が提案した記述長最小化(Minimum Description Length, MDL)によるコミュニティ検出手法。グラフ上のランダムウォークの情報伝達を、コミュニティ名と頂点名という2階層で符号化し、記述長を最小にする分割を探索する。異なるサイズのコミュニティに対して modularity 最適化より優れる([[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] p.52-53)。 > "The method appears superior than modularity optimization, especially when communities are of different sizes."(同 p.53) Rosvall(2007)のコードは http://www.tp.umu.se/~rosvall/code.html で公開されている。Rosvall et al.(2009) は Blondel et al. の高速貪欲法を採用して有向・重み付きグラフに拡張し、テレポーテーション確率 τ で Google PageRank 同様にエルゴード性を担保する(同 p.53)。この記述長最小化の系譜は、のちの Infomap 手法の前身にあたる。 Sun, Y. et al. による初期の類似手法(二部グラフの時間発展を扱う。第XIII章で詳述予定)や、Chakrabarti, D. による MDL 原理の隣接行列ブロック対角化への応用も同系統に位置づく(同 p.52-53)。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] — 本手法を扱う章。 - [[@2010__PhysRep__Community detection in graphs - Chapter X Alternative methods]] — 情報理論的手法(information bottleneck 法)の議論を引き継ぐ次章。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] — Rosvall と Bergstrom による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。