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