Skip to main content
Article
A Distributed Algorithm For Identifying Strongly Connected Components On Incremental Graphs
Proceedings - Symposium on Computer Architecture and High Performance Computing
  • S. Srinivasan
  • A. Khanda
  • S. Srinivasan
  • A. Pandey
  • S. (Sajal) K. Das, Missouri University of Science and Technology
  • S. Bhowmick
  • B. Norris
Abstract

Incremental graphs that change over time capture the changing relationships of different entities. Given that many real-world networks are extremely large, it is often necessary to partition the network over many distributed systems and solve a complex graph problem over the partitioned network. This paper presents a distributed algorithm for identifying strongly connected components (SCC) on incremental graphs. We propose a two-phase asynchronous algorithm that involves storing the intermediate results between each iteration of dynamic updates in a novel meta-graph storage format for efficient recomputation of the SCC for successive iterations. To the best of our knowledge, this is the first attempt at identifying SCC for incremental graphs across distributed compute nodes. Our experimental analysis on real and synthesized graphs shows up to 2.8x performance improvement over the state-of-the-art by reducing the overall memory utilized and improving the communication bandwidth.

Department(s)
Computer Science
Comments

National Science Foundation, Grant 2104076

Keywords and Phrases
  • Distributed systems,
  • Dynamic graphs,
  • Strongly connected components
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
1-1-2023
Publication Date
01 Jan 2023
Disciplines
Citation Information
S. Srinivasan, A. Khanda, S. Srinivasan, A. Pandey, et al.. "A Distributed Algorithm For Identifying Strongly Connected Components On Incremental Graphs" Proceedings - Symposium on Computer Architecture and High Performance Computing (2023) p. 109 - 118 ISSN: 1550-6533
Available at: http://works.bepress.com/sajal-das/329/