Triangle listing in massive networks and its applications

S Chu, J Cheng - Proceedings of the 17th ACM SIGKDD international …, 2011 - dl.acm.org
S Chu, J Cheng
Proceedings of the 17th ACM SIGKDD international conference on Knowledge …, 2011dl.acm.org
Triangle listing is one of the fundamental algorithmic problems whose solution has
numerous applications especially in the analysis of complex networks, such as the
computation of clustering coefficient, transitivity, triangular connectivity, etc. Existing
algorithms for triangle listing are mainly in-memory algorithms, whose performance cannot
scale with the massive volume of today's fast growing networks. When the input graph
cannot fit into main memory, triangle listing requires random disk accesses that can incur …
Triangle listing is one of the fundamental algorithmic problems whose solution has numerous applications especially in the analysis of complex networks, such as the computation of clustering coefficient, transitivity, triangular connectivity, etc. Existing algorithms for triangle listing are mainly in-memory algorithms, whose performance cannot scale with the massive volume of today's fast growing networks. When the input graph cannot fit into main memory, triangle listing requires random disk accesses that can incur prohibitively large I/O cost. Some streaming and sampling algorithms have been proposed but these are approximation algorithms. We propose an I/O-efficient algorithm for triangle listing. Our algorithm is exact and avoids random disk access. Our results show that our algorithm is scalable and outperforms the state-of-the-art local triangle estimation algorithm.
ACM Digital Library