Fast algorithm for detecting community structure in networks

Finding and evaluating comunity structure in networksと同じ著者の論文(共著ではない)，前の論文では最短路betweenessの大きいものを切ってくというやり方で，1つのグラフを複数の部分グラフに分けてくという方法をとったが，今回はそのときのクラスタの評価に用いたmodularityという値に着目して，最初はn個のクラスタがある状態からどんどんつなげていって最終的に１つのグラフになるようなボトムアップな方法を用いる．

こうすることによって，前の論文の方法が計算時間がO(VE^2)であるのに対して，この方法だとO(VE)で終了する(ただし，今回のものも前回のものもグラフが疎であるという仮定があるので|E|は|V|の高々定数倍)

実際にこの方法をノード数50000ぐらいの論文の共著者ネットワークの解析に適用している．