DocumentCode :
1918825
Title :
Abstract: Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients
Author :
Arifuzzaman, Shaikh ; Khan, Mahrukh ; Marathe, M.
Author_Institution :
Dept. of Comput. Sci., Virginia Tech, Blacksburg, VA, USA
fYear :
2012
fDate :
10-16 Nov. 2012
Firstpage :
1448
Lastpage :
1449
Abstract :
We present MPI-based parallel algorithms for counting triangles and computing clustering coefficients in massive networks. Counting triangles is important in the analysis of various networks, e.g., social, biological, web etc. Emerging massive networks do not fit in the main memory of a single machine and are very challenging to work with. Our distributed-memory parallel algorithm allows us to deal with such massive networks in a time- and space-efficient manner. We were able to count triangles in a graph with 2 billions of nodes and 50 billions of edges in 10 minutes. Our parallel algorithm for computing clustering coefficients uses efficient external memory aggregation. We also show how edge sparsification technique can be used with our parallel algorithm to find approximate number of triangles without sacrificing the accuracy of estimation. In addition, we propose a simple modification of a state-of-the-art sequential algorithm that improves both runtime and space requirement.
Keywords :
graph theory; parallel algorithms; MPI; computing clustering coefficient; counting triangle; distributed-memory parallel algorithm; edge sparsification technique; external memory aggregation; massive network; sequential algorithm; Clustering Coefficients; HPC; Massive Graphs; Parallel Algorithms; Triangles;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion:
Conference_Location :
Salt Lake City, UT
Print_ISBN :
978-1-4673-6218-4
Type :
conf
DOI :
10.1109/SC.Companion.2012.250
Filename :
6496033
Link To Document :
بازگشت