Density-friendly graph decomposition (WWW '15)

Nikolaj Tatti and Aristides Gionis.

概要

k-core分解はグラフの階層的構造を見る上で基本的な操作として知られているが、 k-core分解で得られた部分グラフの内部が密になっているとは限らない。この論文ではlocally-denseという指標をグラフに対して定義して、 k-core分解に似たlocally-dense decompositionというものを提案する。 locally-dense decompositionをO(|V|^2|E|)時間で求める実験的に高速なアルゴリズムと線形時間の２近似アルゴリズムを提案する。 locally-dense decompositionとcore decompositionを実行時間と得られた部分グラフのdensityを実験して比較した結果、locally-dense decompositionの方が良いということがわかった。（どのくらい良いかは読んでないのでわからない・・・）

locally-denseとは？

locally-denseとはその部分グラフの内部が外部より高いdensityを持つ部分グラフのこと。(部分グラフXのdensityは\(\frac{|E(X)|}{|X|} \)。 ) 部分グラフ\( W \subseteq V \)がlocally denseであるとは\(X \subseteq W \)と\(Y \subseteq V \setminus W \)で \( d(X, W \setminus X) \le d(Y, W) \)を満たすものが存在しないということ。( \(d(X, Y) = \frac{E(X) \cup E(X, Y)}{|X|} \) )　雰囲気としては１つの頂点からスタートして順番に頂点を付け加えていったときに、最初の方に加えた頂点集合\( X \)の方が後で加えた頂点集合\( Y \)よりも高いdensityに貢献しているということだろうか。

locally-dense decompositionとは以下の性質を持つ。（詳細は知らない）

より内側にある部分グラフの方が外側よりも密
一番内側にある部分グラフがdensest subgraphに対応
効率よく計算できる

Goldbergによる最小カットを用いたdensest subgraphの計算アルゴリズムを拡張して厳密計算できるらしい。