Finding and evaluating comunity structure in networks

グラフが与えられた時に以下のような方法でクラスタリングする．

1. 全ての枝に対してbetweennessを計算する
2. 最も大きなbetweennessをもつ枝を除去する
3. betwennessを再計算する.
4. 2にもどる

betweennessの定義は色々あり，一つの定義としては任意の2点間の最短路をすべて取ってきたときに，その枝を通る最短路の数として定義するものがある．こうするとコミュニティを結ぶ紐帯のような枝を通る最短路は多いのでbetweennessは大きくなる．ここで得られたクラスタの評価方法としてはこの論文ではクラスタ間の接続行列を書いた時，そのtraceを基準にしている(正確にはtraceから全部の要素の和を引いたもの)