A Distributed Algorithm for Identifying Strongly Connected Components on Incremental Graphs

  • S. Srinivasan University of Oregon
  • A. Khanda Missouri University of Science and Technology
  • S. Srinivasan University of Oregon / University of North Texas
  • A. Pandey Bowie State University
  • S. K. Das Missouri University of Science and Technology
  • S. Bhowmick Bowie State University
  • B. Norris University of Oregon

Resumo


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.
Palavras-chave: Dynamic graphs, Distributed systems, Strongly connected components
Publicado
17/10/2023
Como Citar

Selecione um Formato
SRINIVASAN, S.; KHANDA, A.; SRINIVASAN, S.; PANDEY, A.; DAS, S. K.; BHOWMICK, S.; NORRIS, B.. A Distributed Algorithm for Identifying Strongly Connected Components on Incremental Graphs. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 35. , 2023, Porto Alegre/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 109-118.