Number of triangles in a graph is a useful metric in network analysis. It is particularly useful in analysis of social networks. As the size of social networks is increasing day by day, such metrics of the graphs need to be computed quickly and efficiently to analyse them properly.
This project is done as part of the course Parallel Programming Paradigm offered by Prof. Sharat Chandran
Find our project proposal here
- We have implemented various sequential algorithms for counting triangles in undirected graph
- We chose the best sequential and parallelizable algorithm and implemented in MPI and Cuda
- Datasets for testing are taken from SNAP
- Basic ideas for starting are taken from Thesis of Thomas Schank and CMU Parallelism Competition