Fully dynamic algorithm for top-k densest subgraphs

Muhammad Anis Uddin Nasir, Aristides Gionis, Gianmarco De Francisci Morales, Sarunas Girdzijauskas

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

11 Citations (Scopus)

Abstract

Given a large graph, the densest-subgraph problem asks to find a subgraph with maximum average degree. When considering the top-k version of this problem, a nattive solution is to iteratively find the densest subgraph and remove it in each iteration. However, such a solution is impractical due to high processing cost. The problem is further complicated when dealing with dynamic graphs, since adding or removing an edge requires re-running the algorithm. In this paper, we study the top-k densest-subgraph problem in the sliding-window model and propose an efficient fully-dynamic algorithm. The input of our algorithm consists of an edge stream, and the goal is to find the node-disjoint subgraphs that maximize the sum of their densities. In contrast to existing state-of-the-art solutions that require iterating over the entire graph upon any update, our algorithm profits from the observation that updates only affect a limited region of the graph. Therefore, the top-k densest subgraphs are maintained by only applying local updates. We provide a theoretical analysis of the proposed algorithm and show empirically that the algorithm offen generates denser subgraphs than state-of-the-art competitors. Experiments show an improvement in efficiency of up to five orders of magnitude compared to state-of-the-art solutions.

Original languageEnglish
Title of host publicationCIKM 2017 - Proceedings of the 2017 ACM Conference on Information and Knowledge Management
PublisherACM
Pages1817-1826
Number of pages10
VolumePart F131841
ISBN (Electronic)9781450349185
DOIs
Publication statusPublished - 6 Nov 2017
MoE publication typeA4 Article in a conference publication
EventACM International Conference on Information and Knowledge Management - Singapore, Singapore
Duration: 6 Nov 201710 Nov 2017
Conference number: 26

Conference

ConferenceACM International Conference on Information and Knowledge Management
Abbreviated titleCIKM
CountrySingapore
CitySingapore
Period06/11/201710/11/2017

Fingerprint Dive into the research topics of 'Fully dynamic algorithm for top-k densest subgraphs'. Together they form a unique fingerprint.

Cite this