This project implements several exact and approximate triangle counting algorithms using Python and explores their scalability properties on different real-world data sets, retrieved from SNAP.
The implemented exact algorithms include the Brute-Force algorithm, the Node-Iterator algorithm, and the Compact-Forward algorithm, while the DOULION algorithm is used for approximate triangle counting. Additionally, the streaming algorithm TRIEST is explored for triangle counting in dynamic graphs.
Our experiments evaluate the performance of each algorithm on different data sets and compare their efficiency in terms of time and space complexity.
The results of our study provide a comprehensive evaluation of each algorithm and its scalability properties, which will be valuable for researchers and practitioners who work with large graphs and are interested in efficient triangle counting algorithms.
*In the notebook, one can find basic theory, besides code.