Streaming and Batch Algorithms for Truss Decomposition

Venkata Rohit Jakkula, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Truss decomposition is a method used to analyze large sparse graphs in order to identify successively better connected subgraphs. Since in many domains the underlying graph changes over time, its associated truss decomposition needs to be updated as well. This work focuses on the problem of incrementally updating an existing truss decomposition and makes the following three significant contributions. First, it presents a theory that identifies how the truss decomposition can change as new edges get added. Second, it develops an efficient incremental algorithm that incorporates various optimizations to update the truss decomposition after every edge addition. These optimizations are designed to reduce the number of edges that are explored by the algorithm. Third, it extends this algorithm to batch updates (i.e., where the truss decomposition needs to be updated after a set of edges are added), which reduces the overall computations that need to be performed. We evaluated the performance of our algorithms on real-world datasets. Our incremental algorithm achieves over 250000x average speedup for inserting an edge in a graph with 10 million edges relative to the non-incremental algorithm. Further, our experiments on batch updates show that our batch algorithm consistently performs better than the incremental algorithm.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 1st International Conference on Graph Computing, GC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages51-59
Number of pages9
ISBN (Electronic)9781728141299
DOIs
StatePublished - Sep 2019
Event1st International Conference on Graph Computing, GC 2019 - Laguna Hills, United States
Duration: Sep 25 2019Sep 27 2019

Publication series

NameProceedings - 2019 1st International Conference on Graph Computing, GC 2019

Conference

Conference1st International Conference on Graph Computing, GC 2019
CountryUnited States
CityLaguna Hills
Period9/25/199/27/19

Keywords

  • batch graph algorithms
  • network science
  • streaming graph algorithms
  • truss
  • truss decomposition

Fingerprint Dive into the research topics of 'Streaming and Batch Algorithms for Truss Decomposition'. Together they form a unique fingerprint.

  • Cite this

    Jakkula, V. R., & Karypis, G. (2019). Streaming and Batch Algorithms for Truss Decomposition. In Proceedings - 2019 1st International Conference on Graph Computing, GC 2019 (pp. 51-59). [9030981] (Proceedings - 2019 1st International Conference on Graph Computing, GC 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GC46384.2019.00016