Densest subgraph in dynamic graph streams

DOI10.1007/978-3-662-48054-0_39MaRDI QIDQ2946417zbMATH OpenOpenAlexFDO

Authors Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.04417

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Other nonclassical models of computation (68Q09) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbitrary sequence of edge insertions and deletions and the goal is to analyze properties of the resulting graph given memory that is sub-linear in the size of the stream. We present a single-pass algorithm that returns a $(1+epsilon)$ approximation of the maximum density with high probability; the algorithm uses $O(epsilo{n}^{-2}npolylogn)$ space, processes each stream update in $polylog(n)$ time, and uses $poly(n)$ post-processing time where $n$ is the number of nodes. The space used by our algorithm matches the lower bound of Bahmani et al.~(PVLDB 2012) up to a poly-logarithmic factor for constant $epsilon$. The best existing results for this problem were established recently by Bhattacharya et al.~(STOC 2015). They presented a $(2+epsilon)$ approximation algorithm using similar space and another algorithm that both processed each update and maintained a $(4+epsilon)$ approximation of the current maximum density in $polylog(n)$ time per-update.

Recommendations

• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space
• Dense subgraphs on dynamic networks

Cited in

(22)

• Dynamic graph stream algorithms in \(o(n)\) space
• Sublinear update time randomized algorithms for dynamic graph regression
• Better streaming algorithms for the maximum coverage problem
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Single-pass streaming algorithms to partition graphs into few forests
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Dense subgraphs on dynamic networks
• Optimality of linear sketching under modular updates
• Brief announcement
• Revisiting maximum satisfiability and related problems in data streams
• Distributed dense subgraph detection and low outdegree orientation
• Practical parallel algorithms for near-optimal densest subgraphs on massive graphs
• Graph coloring via degeneracy in streaming and other space-conscious models
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• Massively parallel computation in a heterogeneous regime
• Rounds vs. communication tradeoffs for maximal independent sets
• Optirefine: densest subgraphs and maximum cuts with k refinements
• Improved algorithms for maximum coverage in dynamic and random order streams
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Approximating densest subgraph in geometric intersection graphs
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism
• Sublinear space graph algorithms in the continual release model

This page was built for publication: Densest subgraph in dynamic graph streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946417)