「Querying K-Truss Community in Large and Dynamic Graph」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Querying K-Truss Community in Large and Dynamic Graph
- Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, Jeffrey Xu Yu
- SIGMOD 2014
- (α, γ)-OCS
-- γ-quasi-k-クリークを頂点とする
--- γ{k choose 2}本以上のk頂点部分グラフ
-- ↑を各頂点として，α頂点以上共有なら辺を張る
-- ヘボい！
- k-truss
-- どの辺も少なくともk-2個の三角形に属する極大な部分グラフ
-- 辺の連結: どの2辺も三角形の連結で到達可能
- k-truss コミュニティ
-- vを含むk-truss コミュニティを列挙
- 利点
-- パラメタが1つ
-- 多項式時間
- k-truss コミュニティクエリ
-- 2つの索引
-- Simple index, Novel index
- 性質
-- ある辺を含むk-truss コミュニティは唯一
- Simple Index
-- τ(e) := eを含む部分グラフでeの属する三角形の数がτ(e)以上，みたいな を計算
-- τ(e)を全部計算
-- クエリの答え方
--- vを端点とする辺からτ(e)≧kとなるように三角形をたどっていく
--- 早そう
- Novel Index
-- τ(e)<kにアクセスするのが無駄
&tags()
2014/12/06
