Finding community structure in very large networks

まだ，中身には目を通してないのだが，ここで提案されているアルゴリズムによりO(n(log^2 n))でコミュニティの抽出がおこなえる(nはノード数，グラフは疎)

大規模なネットワークな例としてはamazon.comの商品409,687点と，"この商品を買っている人は〜"のリンク2,464,630をグラフと見てコミュニティの抽出を行っている．

追記：

modularityの増減だけに注目してやり，データ構造を適切に設定するとFast algorithm for detecting community structure in networksと方針は同じgreedy algorithmで計算量がO(mdlogn)に落ちる．(mは枝の本数，dはコミュニティの樹形図の深さ ,通常m〜n,d〜logn)