← 研踪 PaperTrailarXiv:2611.09649 · v1
Parallel Algorithms for Higher-Order Temporal H-Index Computation
首次提交 2026-11-06 23:59
版本更新 2026-11-06 23:59
雷达观测 2026-11-09 13:22
摘要
Ranking vertices by importance is a fundamental task in network mining. The H-index provides such a ranking by asking how many neighbors are themselves well connected; its higher-order temporal variant recursively applies this idea over time-respecting neighborhoods in temporal networks. Scaling its computation is difficult because the existing streaming algorithm intertwines temporal processing with H-index order, incurring maximum-degree-dependent costs and exposing little parallelism. We show that the temporal dependencies can instead be resolved once: each edge's time-dependent lookup is mapped to a fixed successor position, turning every H-index order into a parallel gather followed by a segmented suffix-H computation. Based on this reformulation, we derive a linear-work suffix-H algorithm, a parallel multicore CPU implementation, degree-adaptive GPU kernels, and a multi-GPU scheme that exchanges only distinct remotely queried states. Experiments on synthetic and real-world temporal graphs show that the reformulation alone is substantially faster than the streaming algorithm, and that GPUs add order-round speedups exceeding an order of magnitude over our multicore implementation on synthetic inputs with up to one billion temporal edges. On a 636M-edge Reddit network, eight GPUs compute 128 orders in 3.6 s of round time, whereas the streaming algorithm does not finish within an hour even at order 8.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 23:59 · 最新观测版本
Parallel Algorithms for Higher-Order Temporal H-Index Computation
Ranking vertices by importance is a fundamental task in network mining. The H-index provides such a ranking by asking how many neighbors are themselves well connected; its higher-order temporal variant recursively applies this idea over time-respecting neighborhoods in temporal networks. Scaling its computation is difficult because the existing streaming algorithm intertwines temporal processing with H-index order, incurring maximum-degree-dependent costs and exposing little parallelism. We show that the temporal dependencies can instead be resolved once: each edge's time-dependent lookup is mapped to a fixed successor position, turning every H-index order into a parallel gather followed by a segmented suffix-H computation. Based on this reformulation, we derive a linear-work suffix-H algorithm, a parallel multicore CPU implementation, degree-adaptive GPU kernels, and a multi-GPU scheme that exchanges only distinct remotely queried states. Experiments on synthetic and real-world temporal graphs show that the reformulation alone is substantially faster than the streaming algorithm, and that GPUs add order-round speedups exceeding an order of magnitude over our multicore implementation on synthetic inputs with up to one billion temporal edges. On a 636M-edge Reddit network, eight GPUs compute 128 orders in 3.6 s of round time, whereas the streaming algorithm does not finish within an hour even at order 8.
查看此版本解读 →查看此版本原文 ↗