COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks - todo314 @ ウィキ

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
• 大まかに
  1. グラフを数列へマッピング
  2. 数列上で部分列マイニング
  3. 候補をグラフ上で調査

数列にマッピング

• (u,v,t)→(deg(u), deg(v))にして，tでソート
• αがβの部分列…
  • 対応する位置ではα側の次数ペアの方が小さい

部分列マイニング

• Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database
• が使えるように頑張る

SIGMOD モチーフ

2015/11/12