  Listing all triangles is a fundamental graph operation. Triangles can have
important interpretations in real-world graphs, especially social and other
interaction networks. 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?
  We study one of the most prevalent algorithms used by practitioners. A
trivial algorithm enumerates all paths of length $2$, and checks if each such
path is incident to a triangle. A good heuristic is to enumerate only those
paths of length $2$ where the middle vertex has the lowest degree. It is easily
implemented and is empirically known to give remarkable speedups over the
trivial algorithm.
  We study the behavior of this algorithm over graphs with heavy-tailed degree
distributions, a defining feature of real-world graphs. The erased
configuration model (ECM) efficiently generates a graph with asymptotically
(almost) any desired degree sequence. We show that the expected running time of
this algorithm over the distribution of graphs created by the ECM is controlled
by the $\ell_{4/3}$-norm of the degree sequence. Norms of the degree sequence
are a measure of the heaviness of the tail, and it is precisely this feature
that allows non-trivial speedups of simple triangle enumeration algorithms. As
a corollary of our main theorem, we prove expected linear-time performance for
degree sequences following a power law with exponent $\alpha \geq 7/3$, and
non-trivial speedup whenever $\alpha \in (2,3)$.
