Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
复制标题
DOI：
10.1145/3447548.3467374
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Noujan Pashanasangi;C. Seshadhri
中科院分区：
文献类型：
--
作者：
Noujan Pashanasangi;C. Seshadhri
三角计数是网络分析中的一项基本技术，在各种输入模型中都受到了广泛的关注。绝大多数三角形计数算法都是针对静态图形的。然而，许多现实世界的图是有向的和时态的，其中边带有时间戳。时态三角形会产生更多的信息，因为它们既考虑了图形拓扑结构，又考虑了时间戳。时间三角计数已经看到了一些最新的结果，但对时间三角形有不同的定义。在所有情况下，时间三角形模式都会对边(在三角形中)之间的时间间隔施加约束。我们定义了一个通用的概念(δ1，3，δ1，2，δ2，3)-时间三角形，它允许所有的边对单独的时间约束。我们的主要结果是一种新的算法DOTTT(退化定向的时态三角形累加器)，它精确地计数(δ1，3，δ1，2，δ2，3)-时态三角形的所有有向变量。利用经典的简并序思想和仔细的组合论证，我们可以证明DOTTT运行在O(mκłogm)时间内，其中m是(时间)边数，κ是图的简并度(最大核数)。根据LOG系数，这与最佳静态三角形计数器的运行时间相匹配。此外，这种运行时间比现有的更好。DOTTT具有出色的实用性能，运行速度是现有最先进的临时三角形计数器的两倍(也更通用)。例如，DOTTT在一台商用机器上，在不到一小时的时间内计算比特币时间网络中的所有类型的时间查询，具有5亿条边。
Triangle counting is a fundamental technique in network analysis, that has received much attention in various input models. The vast majority of triangle counting algorithms are targeted to static graphs. Yet, many real-world graphs are directed and temporal, where edges come with timestamps. Temporal triangles yield much more information, since they account for both the graph topology and the timestamps. Temporal triangle counting has seen a few recent results, but there are varying definitions of temporal triangles. In all cases, temporal triangle patterns enforce constraints on the time interval between edges (in the triangle). We define a general notion (δ1,3, δ1,2, δ2,3)-temporal triangles that allows for separate time constraints for all pairs of edges. Our main result is a new algorithm, DOTTT (Degeneracy Oriented Temporal Triangle Totaler), that exactly counts all directed variants of (δ1,3, δ1,2, δ2,3)-temporal triangles. Using the classic idea of degeneracy ordering with careful combinatorial arguments, we can prove that DOTTT runs in O(mκłog m) time, where m is the number of (temporal) edges and κ is the graph degeneracy (max core number). Up to log factors, this matches the running time of the best static triangle counters. Moreover, this running time is better than existing. DOTTT has excellent practical behavior and runs twice as fast as existing state-of-the-art temporal triangle counters (and is also more general). For example, DOTTT computes all types of temporal queries in Bitcoin temporal network with half a billion edges in less than an hour on a commodity machine.