Finding Community Structure in Mega-scale Social Networks

Ken Wakita and Toshiyuki Tsurumi. 2007. Finding community structure in mega-scale social networks: [extended abstract]. In Proceedings of the 16th international conference on World Wide Web (WWW '07). ACM, New York, NY, USA, 1275-1276. DOI=10.1145/1242572.1242805 http://doi.acm.org/10.1145/1242572.1242805

• 問題
  • ソーシャルネットワークのコミュニティ検出
  • モジュラリティ最大化したい系
• CNM アルゴリズム
  • グリーディーにモジュラリティが増える併合を行う
  • 実装してみたらスケールしないんだが？？
  • 調査してみたところ，偏った育ち方をするからダメ
• 提案手法
  • モジュラリティの増え具合に，偏りをかけ算するヒューリスティクスを加えたグリーディ
  • 上手く育って爆速