<span class="var-sub_title">iSpan: Parallel Identification of Strongly Connected Components with Spanning Trees</span> SC18 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

iSpan: Parallel Identification of Strongly Connected Components with Spanning Trees


Authors: Yuede Ji (George Washington University), Hang Liu (University of Massachusetts, Lowell), H. Howie Huang (George Washington University)

Abstract: Detecting strongly connected components (SCCs) in a directed graph is crucial for understanding the structure of graphs. Most real-world graphs have one large SCC that contains the majority of the vertices, and many small SCCs whose sizes are reversely proportional to the frequency of their occurrence. For both types of SCCs, current approaches that rely on depth or breadth first search (DFS or BFS) face the challenges of strict synchronization requirement and high computation cost. In this paper, we advocate a new paradigm of identifying SCCs with simple spanning trees, since SCC detection requires only the knowledge of connectivity among the vertices. We have developed a prototype called iSpan which consists of parallel, relaxed synchronization construction of spanning trees for detecting the large and small SCCs. The evaluations show that iSpan is able to significantly outperform current state-of-the-art DFS and BFS- based methods by average 18× and 4×, respectively.


Presentation: file


Back to Technical Papers Archive Listing