Locally Densest Subgraph Discovery - todo314 @ ウィキ

Locally Densest Subgraph Discovery

• Lu Qin, Rong-Hua Li, Lijun Chang, Chengqi Zhang
• KDD 2015

動機付け

• 皆密部分グラフ大好き
• でかいコミュニティからk個←ツマラン
• 重複回避で似てるの
  • 最密部分グラフ(WSDM'15)
  • クリーク(VLDB'15)

提案概念・手法

• Gがρ-compact
  • 任意のSをGから取り除くと、ρ|S|辺以上消える
• 極大ρ-compact部分グラフを考える
• Locally densest subgraph
  • gがGの極大density(g)-compact部分グラフ
• LDSは互いに素なので、列挙可能

• 「最密部分グラフ抽出(Goldberg'84)⇄消去」するだけでいいのでは？
  • やばお：GでLDS出ないものが、G-VでLDSになることがある
  • 頑張って再判定する
• 総計算時間: $$ (mn(n+m)\log^2 n) $$

• 最適化
  • ρ(v): vを含むLDSのρ
  • これの上限・下限を持っておくと便利
• 後は探索っぽいことをする

実験

• 指標
  • 密度、相対密度、辺密度、直径
• 速度
  • なんか速い、前処理で超小さくなっていそう…

まとめ

• 質の評価が大変だね…

KDD 密部分グラフ

2015/12/17