Online Density Bursting Subgraph Detection from Temporal Graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

  • Lingyang Chu
  • Yanyan Zhang
  • Yu Yang
  • Lanjun Wang
  • Jian Pei

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2353-2365
Journal / PublicationProceedings of the VLDB Endowment
Volume12
Issue number13
Publication statusPublished - Sep 2019

Conference

Title46th International Conference on Very Large Data Bases, VLDB 2020
PlaceJapan
CityVirtual
Period31 August - 4 September 2020

Abstract

Given a temporal weighted graph that consists of a potentially endless stream of updates, we are interested in finding density bursting subgraphs (DBS for short), where a DBS is a subgraph that accumulates its density at the fastest speed. Online DBS detection enjoys many novel applications. At the same time, it is challenging since the time duration of a DBS can be arbitrarily long but a limited size storage can buffer only up to a certain number of updates. To tackle this problem, we observe the critical decomposability of DBSs and show that a DBS with a long time duration can be decomposed into a set of indecomposable DBSs with equal or larger burstiness. We further prove that the time duration of an indecomposable DBS is upper bounded and propose an efficient method TopkDBSOL to detect indecomposable DBSs in an online manner. Extensive experiments demonstrate the effectiveness, efficiency and scalability of TopkDBSOL in detecting significant DBSs from temporal graphs in real applications.

Research Area(s)

  • ALGORITHM, SEQUENCE, SEGMENTS

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)

Online Density Bursting Subgraph Detection from Temporal Graphs. / Chu, Lingyang; Zhang, Yanyan; Yang, Yu et al.

In: Proceedings of the VLDB Endowment, Vol. 12, No. 13, 09.2019, p. 2353-2365.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review