For my masters degree, I worked on a project evaluating random graphs and showed that an algorithm to count all the links in an erased configuration model scaled linearly depending on some conditions.

ITCS ’14: Proceedings of the 5th conference on Innovations in theoretical computer science. January 2014 Pages 225–234https://doi.org/10.1145/2554797.2554819

Citation (authorship is alphabetical): Berry JW, Fostvedt LK, Nordman DJ, Phillips CA, Seshadhri C, Wilson AG. Why do simple algorithms for triangle enumeration work in the real world?. InProceedings of the 5th conference on Innovations in theoretical computer science 2014 Jan 12 (pp. 225-234).

Abstract:

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? 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 l_4/3-norm of the degree sequence. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent α ≥ 7/3, and non-trivial speedup whenever α ∈ (2,3).