Home > Papers

 
 
Enumerate Strongly Connected Components of Large-scale Graph with MapReduce
Lu Lv * #,Lei Xie
Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing,100876
*Correspondence author
#Submitted by
Subject:
Funding: none
Opened online:31 December 2012
Accepted by: none
Citation: Lu Lv,Lei Xie.Enumerate Strongly Connected Components of Large-scale Graph with MapReduce[OL]. [31 December 2012] http://en.paper.edu.cn/en_releasepaper/content/4502357
 
 
Enumerating strongly connected components in directed graph is the fundamental problem of graph theory. The standard serial algorithm for strongly connected components is based on depth first search, which is difficult to parallelize for large scale graph. In this paper, we propose a nearly linear parallel bi-directional label propagation algorithm to enumerate strongly connected components of large scale graph on MapReduce framework. The algorithm is suitable for large scale graphs and the experiment shows its efficiency and scalability.
Keywords:Graph Mining; Strongly Connected Component; LPA; MapReduce
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 843
Bookmarked 0
Recommend 5
Comments Array
Submit your papers