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