Fast Triangle Detection and Enumeration in Undirected Graphs: The Aegypti Algorithm

The triangle finding problem is a cornerstone of complex network analysis, serving as the primitive for computing clustering coefficients and transitivity. This paper presents \( \texttt{Aegypti} \), a practical algorithm for triangle detection and enumeration in undirected graphs. By combining a descending degree-ordered vertex-iterator with a hybrid strategy that adapts to graph density, \( \texttt{Aegypti} \) ensures a worst-case runtime of \( \mathcal{O}(m^{3/2}) \) for full enumeration, matching the theoretical limit for listing algorithms. Furthermore, we analyze the detection variant (\( \texttt{first_triangle}=\text{True} \)), proving that sorting by non-increasing degree enables immediate termination in dense instances and sub-millisecond detection in scale-free networks. Extensive experiments confirm speedups of \( 10\times \) to \( 400\times \) over NetworkX, establishing \( \texttt{Aegypti} \) as the fastest pure-Python approach currently available.