This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyuce et al., PVLDB 2018). The key to the theoretical efficiency of our algorithm is a new lemma that bounds the amount of work done when peeling cliques from the graph, combined with the use of a theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyuce et al., and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.
翻译:本文研究核心分解问题, 事实证明, 核心分解问题对于在图表中找到密集的子结构是有用的。 我们展示了一种新的平行算法, 在理论和实践上都是高效的。 我们的算法实现了与最佳顺序算法相匹配的工作复杂性, 同时也有了低深度( 平行运行时间), 这极大地改进了唯一存在的平行核心分解算法( Sariyuce 等人, PVLDB 2018) 。 我们算法的理论效率的关键在于一种新的利玛, 将从图表中剥离晶体时完成的工作量绑在一起, 再加上使用一种具有理论效率的平行算法来进行分类列表和打桶。 我们引入了几种新的实际优化, 包括一个新的多层次散货表结构结构, 以高效的方式存储关于岩层空间分解法的信息, 以及一种对结构缓存效率进行翻转的技术。 在一台30个核心机器上双向超高速阅读真实世界的图形上, 我们实现了55x速度, 将州级的平行核心分解算法, 而不是Staryal decomgradeal ligal listal ligal listal listal listal listal list listal listal listal ligal ligal ligal ligalpal