text: 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 @math , and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length @math 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 @math -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 @math , and non-trivial speedup whenever @math .
  @cite_30: A graph-constructive approach to solving systems of geometric constraints capable of effeciently handling well-constrained, overconstrained, and underconstrained configurations is presented. The geometric constraint solver works in two phases: in the analysis phase the constraint graph is analyzed and a sequence of elementary construction steps is derived, and then in the construction phase the sequence of construction steps in actually carried out. The analysis phase of the algorithm is described in detail, its correctness is proved, and an efficient algorith to realized it is presented. The scope of the graph analysis is then extended by utilizing semantic information in the form of anlge derivations, and by extending the repertoire of the construction steps. Finally, the construction phase is briefly discussed.
  @cite_4: Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barth ' e lemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than @math edges, where @math is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barth ' e lemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than @math total edge weight, where @math is the total edge weight in the network and @math is the maximum weight of an inter-community edge. If @math is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low @math , we modify the CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.
summary: Explicit triangle enumerations have been used for various applications on large graphs. Fudos and Hoffman @cite_30 use triangle enumeration for a graph-based approach for solving systems of geometric constraints. @cite_4 touch every triangle as part of their community detection algorithm for large graphs.