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

Source abstract

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}$ achieves a worst-case runtime of $\mathcal{O}(m^{3/2})$ for full enumeration, which matches the bound established by Chiba and Nishizeki for arboricity-based listing algorithms. For the detection variant (\( \texttt{first_triangle}=\text{True} \)), we prove that sorting by non-increasing degree enables early termination in $\mathcal{O}(n\log n + d_{\max}^2)$ worst-case time when the maximum-degree vertex participates in a triangle, where the quadratic factor in $d_{\max}$ reduces to $\mathcal{O}(d_{\max}/C(v_{\max}))$ in expectation when the local clustering coefficient $C(v_{\max}) > 0$. Experiments on complement graphs of DIMACS maximum-clique benchmark instances confirm that detection terminates sub-millisecond on the majority of instances, while the matrix-multiplication baseline requires substantially more time on the same inputs.