Link communities reveal multiscale complexity in networks

Nature 2010.

イントロダクション

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

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

提案手法

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

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

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

実験