Link communities reveal multiscale complexity in networks

Nature 2010.

イントロダクション

overlap を許すコミュニティ列挙，階層構造つき

重複が起こるのは密な部分，そういう時，リンク数コミュ内＜コミュ外になるので，従来の手法では無理（モジュラリティ等）

提案手法

頂点の代わりに辺をクラスタリングすることによる手法．枝の間の類似度を定義し，階層的クラスタリングを行う

重複を許すコミュニティなのに階層構造が得られる！

アルゴリズム

• 枝の類似度を計算し，single-linkage clustering
• 枝の類似度：隣接する枝についてのみ計算．共有してない頂点間のJaccard係数．
  • effective resistance というのもあるけど使わない
• 何を最適化する時点を使うか？
  • 頂点の重複を許すので，前述の通り，モジュラリティは相性が悪い．
  • partition density

実験

• 正解のメタデータつき：Word Assoc（意味），Amazon.com（カテゴリー）