A task-based approach for finding SCCs in real-world graphs on external memory

摘要

Finding strongly connected components (SCCs) in graphs is one of the important research topicsrnof graph data mining. Traditional SCC-finding methods need to load the whole graph intornmain memory before actual processing, whichmakes them inappropriate to process today's largerngraphs. Although it is cost-effective to conductive SCC-finding in the external memory (EM) graphrnprocessing systems, existing EM systems are still inefficient on such workload for 2 reasons:rndata-parallel processing model and inefficient graph mutation mechanism.rnIn this paper, we propose a task-based approach, named as TAS, for finding SCCs in largernreal-world graphs.TAS encapsulates individual graph dataset and the SCC-finding algorithms conductedrnon it as an independent task. By this strategy, different algorithms can be assigned torndifferent datasets according to the stage of processing or the size of the dataset. By graduallyrnremoving unneeded data, ie, the known SCCs, with an efficient graph mutation method, TAS continuouslyrnreduces the scale of the problem to accelerate processing. Performance evaluation onrnlarge real-world graphs show that TAS greatly outperforms existing EMsolutions on finding SCCsrn(eg, 55.2x faster than GraphChi and 40.3x faster than X-Stream).