COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks
-
Saket Gurukar, Sayan Ranu, Balaraman Ravindran
-
SIGMOD 2015
概要
-
テンポラルネットワーク上で頻出するモチーフを抽出したい
-
次数列に変換,部分列マイニングで絞る
Frequent subgraph mining
-
A->B(1)とB->C(2)
-
A->B(2)とB->C(1)
-
違うお
-
グラフ同型問題的なので,時間的関係を考慮するのはちょいやばめ?
-
マイニング的手法…厳密でない
定義
-
辺はある時刻に瞬間的に発生
-
$$ |t_i - t_j| \leq \Delta T $$なら2辺が関係してる
-
この関係で連結性とかを考える
-
向きは考えない
-
時間的同型
-
sup(H)…HがGに時間的同型で出てくる個数
-
Range Query: sup(H)≧τなHを求める
-
Top-k Query: sup(H)がtop-kのHを求める
提案手法 COMMIT
-
COMMIT: COMmunication Motifs in InTeraction Networks
-
大まかに
-
グラフを数列へマッピング
-
数列上で部分列マイニング
-
候補をグラフ上で調査
数列にマッピング
-
(u,v,t)→(deg(u), deg(v))にして,tでソート
-
αがβの部分列…
部分列マイニング
-
Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database
-
が使えるように頑張る
SIGMOD モチーフ
2015/11/12
最終更新:2015年11月12日 19:05