highest betweenness

ネットワークにおいて、ノードをいくつかのグループ（クラスタ）に分割するための手法として、リンク（辺）の betweenness を使うのがある。betweenness とは、すべてのノード（頂点）のペアについての最短経路が何回そのリンクを通るかというもの。密接に結びついているノード同士では直接リンクで結ばれていたりするので betweenness は小さくなり、逆に弱い紐帯となっているリンクでは、そこを通ることがノード間の経路の近道になっていることが多いので、betweenness は大きくなる。そこで、betweenness が大きな辺から徐々にのぞいていくと（実際のルールはもうちょっと複雑、派生ルールもいくつかあるみたい）、いくつかの成分に分かれるので、それをクラスタと見なすというもの。いわゆる社会ネットワークにおいてコミュニティを発見する手法としても用いられているみたい。その筋では有名な手法なのかな？

JUNGのAPIを眺めていて発見。Pajekにも実装されているみたいだが、詳細はまだよくわからない。