Change search
ReferencesLink to record
Permanent link

Direct link
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
The Institute of Mathematical Sciences, Chennai, India..
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4468-2675
Harvard University.
2015 (English)In: STOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, ACM Press, 2015, 173-182 p.Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
ACM Press, 2015. 173-182 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-165848DOI: 10.1145/2746539.2746592ScopusID: 2-s2.0-84958762411OAI: diva2:808915
STOC 2015: 47th Annual Symposium on Theory of Computing, June 15 - 17 2015,Portland, OR, USA

QC 20150811

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2015-08-11Bibliographically approved

Open Access in DiVA

fulltext(525 kB)21 downloads
File information
File name FULLTEXT01.pdfFile size 525 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusConference websiteACM digital library

Search in DiVA

By author/editor
Na Nongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 21 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 60 hits
ReferencesLink to record
Permanent link

Direct link