Online Search of Overlapping Communities

Online Search of Overlapping Communities

  • Wanyun Cui, Yanghua Xiao, Haixun Wang, Yiqi Lu, Wei Wang
  • SIGMOD 2013

問題

  • コミュニティの考え方
  • k-clique グラフを頂点とする
  • ↑の頂点ペアがk-1頂点を共有しているたら辺を張る
  • それでの連結成分がコミュニティになる
  • 定義
  • 入力:頂点v,整数k
  • 出力:vが属するk-cliqueコミュニティ(の列挙)
  • 頂点ごとにkを変えられる
  • うまお(という主張)
  • これが仕事だ!(という主張)
  • 貢献
    • 問題定義、アルゴリズム設計、実験

(α,γ)-OCS

  • γ-quasi-k-clique
    • 0<=γ<=1
    • γ*Choose(k, 2)本以上の辺を持つk頂点部分グラフ
  • α頂点共有なら辺を張る
  • (k-1, 1)-OCSは元の問題
  • ( ゚д゚)は?意味あんの?
    • 2つの部分グラフの関係(同じコミュニティ? or 別のコミュニティの重なり?)
  • 制約
    • 何か適当に制約を入れた
    • α、γの値の範囲狭まりすぎィ!
    • ほぼα=k-1、γ=1じゃね?
    • 意味なくね?

アルゴリズム

  • 厳密
    • next_clique: vを含むk-cliqueを探す
    • expand: コミュニティ探索
  • 近似
    • 上の近似

実験

  • 環境は家庭用PC
  • (k-1, 1)-OCSでしかも近似アルゴリズムだけ( ゚д゚)は?
  • 比較がやばい
    • vs 既存手法
    • 既存は全頂点平均なのに、提案手法はランダム平均
    • ならしで速いんだから全部やればいいのに

SIGMOD community detection

2013-11-29 15:15:21 (Fri)

最終更新:2013年11月29日 15:15