Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
14 June 2015Published
9 February 2015Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
317532Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
340506Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
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:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us