Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks
-
Yang Zhang, Srinivasan Parthasarathy
-
ICDE 2012
概要
-
Triangle K-Core なる密グラフの概念を提案
-
かなり速く抽出できる
-
しかも動的更新もできる
-
template pattern cliquesをサポート
Triangle K-Core
-
部分グラフG'がTriangle K-Core
-
辺eのMaximum Triangle K-Core
-
eを含む部分グラフG_eでTriangle K-Core numberが最大
-
κ(e)がそのnumber
-
割りとクリークっぽい(kがある程度あれば)
-
定理
-
三角形Tが辺etのmaximum Triangle K-Coreに入っているとする
-
Tの3辺をet, e1, e2とする時,
-
κ(e1),κ(e2)≧κ(et)
-
手法において大事らしい
手法
-
k-coreみたいに各辺eについて三角形の数κ~(e)を保持しておいて
-
κ~(e)の大きい順に決定していって,値を更新していく
-
計算量はO(|#Triangles|+|E|)
動的更新
-
1辺追加/削除されると三角形が沢山追加されたりする
-
そういう三角形を一つ一つ処理する
-
スクラッチよりは速いが…
拡張
実験
-
BiTriDNより速い
-
数千万辺だとBiTriDNは終わらない,T-K-Coreは10分くらい
-
動的更新
-
後は他のオモシロネットワークで実験してみたよお
-
Triangle K-Coreの有用性を出しているっぽい
まとめ
-
結局kが小さければ,カットは小さそうだなあ
-
手法はちょっとおもしろい
ICDE 三角形 密部分グラフ
2014-09-09 02:33:03 (Tue)
最終更新:2014年09月09日 02:33