Extracting Analyzing and Visualizing Triangle K-Core Motifs within Networks

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
    • G'内の各辺がk個以上の三角形に含まれている
  • 辺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辺追加/削除されると三角形が沢山追加されたりする
    • そういう三角形を一つ一つ処理する
    • スクラッチよりは速いが…

拡張

  • DN-graphとの関連も出している

実験

  • BiTriDNより速い
    • 数千万辺だとBiTriDNは終わらない,T-K-Coreは10分くらい
  • 動的更新
    • 100倍位速い
    • LiveJournalで2.4秒
  • 後は他のオモシロネットワークで実験してみたよお
    • Triangle K-Coreの有用性を出しているっぽい

まとめ

  • 結局kが小さければ,カットは小さそうだなあ
    • 薄く三角形が連なる感じ
  • 手法はちょっとおもしろい
    • これより早くするのは…

ICDE 三角形 密部分グラフ

2014-09-09 02:33:03 (Tue)

最終更新:2014年09月09日 02:33