Why do simple algorithms for triangle enumeration work in the real world?
Jonathan W. Berry, Luke Fostvedt, Daniel J. Nordman, Cynthia A. Phillips, Comandur Seshadhri, Alyson G. Wilson · 2014
Triangle enumeration is a fundamental graph operation. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time?