Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification (VLDB'12)

  • ストーリー
    • ツイート → 固有名詞抽出 → リンク → 密グラフ抽出 → 今何が起きているかわかる!!
  • 定式化
    • Graph
      • 重みの付け方:他の論文
    • density
      • avgweight, sqrtdens, avgdegree
    • density が T 以上でサイズが N_max 以下の全ての部分グラフを列挙する
  • アルゴリズム
    • 保持するもの
      • T 以上のもの頂点集合だけじゃなくて,サイズに依存した T_n を作り,T_n 以上を全てを保持
      • ある x が存在して,それを取り除いたものも保持されるように T_n を設定
    • 重み更新
      • δ<0 → 適当に remove
    • 重み更新
      • δ>0 → 適当に成長させる
    • 実装
      • prefix tree を用いて集合を効率的に管理
      • too dense (何を足してもdense)は特別扱い