Abstract: Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients
Authors:
- S. ArifuzzamanSAS. Arifuzzaman
- Maleq KhanMKMaleq Khan
- Madhav MaratheMMMadhav Marathe
- 1 November 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1448-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
This publication has 8 references indexed in Scilit:
- Triangle listing in massive networks and its applications2011
- Counting triangles and the curse of the last reducer2011
- DOULION2009
- Main-memory triangle computations for very large (sparse (power-law)) graphsTheoretical Computer Science, 2008
- Efficient semi-streaming algorithms for local triangle counting in massive graphs2008
- Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study2005
- Birds of a Feather: Homophily in Social NetworksAnnual Review of Sociology, 2001
- Finding and counting given length cyclesAlgorithmica, 1997