Identifying Strongly Connected Components on Distributed Networks

Date and time: 
Wed, Jun 9 2021 - 1:00pm
Sudharshan Srinivasan
University of Oregon
  • Boyana Norris (Chair)
  • Jee Choi
  • Brittany Erickson

Strongly connected components (SCC) are an essential property for understanding the structure of directed networks. Given that many real-world networks are significant, it is often computationally efficient to partition the network over many distributed systems and solve for SCC simultaneously over the partitioned network. In this paper, we present an algorithm for identifying SCC on distributed systems. Our algorithm comprises three steps. In the first step, we locally perform SCC over all partitions. In the second step, we update the partial results across the partitions in a reduced graph form. Lastly, we reapply SCC over the reduced graph at all partitions. The computation within individual partitions is highly scalable using both shared-memory CPU and GPU threads. Our results show the advantages of our approach in the scalability of both performance and memory utilization.