Efficient Densest Subgraph Computation in Evolving Graphs (WWW '15)

Alessandro Epasto, Silvio Lattanzi and Mauro Sozio.

概要

Densest subgraphを動的なグラフで効率良く計算する。densest subgraphと動的なグラフという流行りと流行りを合わせた感じがする。厳密なdensest subgraphの計算は非常に時間がかかるので \(2 + \epsilon \)近似のsubgraphを保持してそれを \( polylog (n + r) \)のならし計算時間で更新していく。このとき辺の挿入は最悪ケースを考慮していて辺の削除は一様ランダムであることを仮定している。

実際の時系列データのタイムウィンドウ内の辺からなるグラフを考えることでインスタンスに対する辺の挿入削除のベンチマークを作っている。実験結果より1B辺のグラフに対する更新が数百マイクロ秒でできることが示された。