On fast parallel detection of strongly connected components (SCC) in small-world graphs
Authors:
Open Access
- 17 November 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-11
Abstract
Detecting strongly connected components (SCCs) in a directed graph is a fundamental graph analysis algorithm that is used in many science and engineering domains. Traditional approaches in parallel SCC detection, however, show limited performance and poor scaling behavior when applied to large real-world graph instances. In this paper, we investigate the shortcomings of the conventional approach and propose a series of extensions that consider the fundamental properties of real-world graphs, e.g. the small-world property. Our scalable implementation offers excellent performance on diverse, small-world graphs resulting in a 5.01x to 29.41x parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads.Keywords
Funding Information
- Army contract (AHPCRC W911NF-07-2-0027-1)
- Defense Advanced Research Projects Agency (US1226344, HR0011-11-C-0007, FA8750-12-2-0335)
- Oracle
- Advanced Micro Devices
- Division of Computing and Communication Foundations (IIS-1247701, CCF-1111943)
- Division of Information and Intelligent Systems (IIS-1247701, CCF-1111943)
- Nvidia
- Huawei Technologies
- Intel Corporation
- Stanford University
This publication has 20 references indexed in Scilit:
- Defining and evaluating network communities based on ground-truth2012
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- Improved Distributed Algorithms for SCC DecompositionElectronic Notes in Theoretical Computer Science, 2008
- Finding strongly connected components in distributed graphsJournal of Parallel and Distributed Computing, 2005
- Ecological subsystems via graph theory: the role of strongly connected componentsOikos, 2005
- Connected Components in Random Graphs with Given Expected Degree SequencesAnnals of Combinatorics, 2002
- Graph structure in the WebComputer Networks, 2000
- On Identifying Strongly Connected Components in Parallel2000
- Depth-first search is inherently sequentialInformation Processing Letters, 1985
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972