The Library
Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
Tools
Tools
Tools
Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon and Tsourakakis, Charalampos (2015) Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: Forty-seventh annual ACM symposium on Theory of computing, Portland, Oregon, USA, 14-17 Jun 2015 . Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of computing pp. 173-182. ISBN 9781450335362. doi:10.1145/2746539.2746592
|
PDF
WRAP-space-time-efficient-algorithm-maintaining-dense-subgraphs-Bhattacharya-2015.pdf - Accepted Version - Requires a PDF viewer. Download (653Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2746539.2746592
Abstract
While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.
Given an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Graph algorithms, Graph theory | |||||||||
| Series Name: | STOC: ACM Symposium on Theory of Computing | |||||||||
| Journal or Publication Title: | Proceedings of the forty-seventh annual ACM symposium on Theory of computing | |||||||||
| Publisher: | ACM | |||||||||
| ISBN: | 9781450335362 | |||||||||
| Official Date: | 14 June 2015 | |||||||||
| Dates: |
|
|||||||||
| Page Range: | pp. 173-182 | |||||||||
| DOI: | 10.1145/2746539.2746592 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | Forty-seventh annual ACM symposium on Theory of computing | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Portland, Oregon, USA | |||||||||
| Date(s) of Event: | 14-17 Jun 2015 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
