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.
Recommended Citation
S. Srinivasan et al., "A Distributed Algorithm For Identifying Strongly Connected Components On Incremental Graphs," Proceedings - Symposium on Computer Architecture and High Performance Computing, pp. 109 - 118, Institute of Electrical and Electronics Engineers, Jan 2023.
The definitive version is available at https://doi.org/10.1109/SBAC-PAD59825.2023.00020
Department(s)
Computer Science
Keywords and Phrases
Distributed systems; Dynamic graphs; Strongly connected components
International Standard Serial Number (ISSN)
1550-6533
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
01 Jan 2023
Comments
National Science Foundation, Grant 2104076