Parallel Triangle Counting and Enumeration Using Matrix Algebra
- 1 May 2015
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2015 IEEE International Parallel and Distributed Processing Symposium Workshop
- p. 804-811
- https://doi.org/10.1109/ipdpsw.2015.75
Abstract
Triangle counting and enumeration are important kernels that are used to characterize graphs. They are also used to compute important statistics such as clustering coefficients. We provide a simple exact algorithm that is based on operations on sparse adjacency matrices. By parallelizing the individual sparse matrix operations, we achieve a parallel algorithm for triangle counting. The algorithm is generalizable to triangle enumeration by modifying the semiring that underlies the matrix algebra. We present a new primitive, masked matrix multiplication, that can be beneficial especially for the enumeration case. We provide results from an initial implementation for the counting case along with various optimizations for communication reduction and load balance.Keywords
This publication has 20 references indexed in Scilit:
- Navigating the maze of graph analytics frameworks using massive graph datasetsPublished by Association for Computing Machinery (ACM) ,2014
- Communication optimal parallel multiplication of sparse random matricesPublished by Association for Computing Machinery (ACM) ,2013
- Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and ExperimentsSIAM Journal on Scientific Computing, 2012
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- The Combinatorial BLAS: design, implementation, and applicationsThe International Journal of High Performance Computing Applications, 2011
- Graph Twiddling in a MapReduce WorldComputing in Science & Engineering, 2009
- A general parallel sparse-blocked matrix multiply for linear scaling SCF theoryComputer Physics Communications, 2000
- Predicting Structure in Sparse Matrix ComputationsSIAM Journal on Matrix Analysis and Applications, 1994
- Sparse Matrices in MATLAB: Design and ImplementationSIAM Journal on Matrix Analysis and Applications, 1992
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970