论文标题
量身定制的顶点订购，以便在大图中更快的三角形列表
Tailored vertex ordering for faster triangle listing in large graphs
论文作者
论文摘要
列表三角形是许多应用程序的基本图形问题，并且大图需要快速算法。顶点订购允许从下部到更高顶点索引边缘取向，而最先进的三角形列表算法则使用它来加速其执行并限制其时间复杂性。但是，仅测试了基本顺序。在本文中，我们表明，研究算法的精确成本而不是其有限的复杂性会导致更快的解决方案。我们介绍了将订购属性与给定算法的运行时间联系起来的成本功能。我们证明它们的最小化是NP-HARD，并提出启发式方法以在降低成本和订购时间之间以不同的权衡获得新的订单。使用最多20亿个边缘的数据集，我们表明我们的启发式方法将三角形的列表加速了38％，当订购已作为输入时，订购时间为16％，当包括订购时间时。
Listing triangles is a fundamental graph problem with many applications, and large graphs require fast algorithms. Vertex ordering allows the orientation of 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 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 38% when the ordering is already given as an input, and 16% when the ordering time is included.
