Tailored vertex ordering for faster triangle listing in large graphs
share
Listing triangles is a fundamental graph problem with many applications, and large graphs require fast algorithms. Vertex ordering allows to orient the edges from lower to higher vertex indices, and state-of-the-art triangle listing algorithms use this to accelerate their execution and to bound their time complexity. Yet, only two basic orderings have been tested. In this paper, we show that studying the precise cost of algorithms instead of their bounded complexity leads to faster solutions. We introduce cost functions that link ordering properties with the running time of a given algorithm. We prove that their minimization is NP-hard and propose heuristics to obtain new orderings with different trade-offs between cost reduction and ordering time. Using datasets with up to two billion edges, we show that our heuristics accelerate the listing of triangles by an average of 30 given as an input, and 15
READ FULL TEXT