nodes

在图形处理单元上检测大型生物网络中有影响力节点的高效并行算法

在生物网络中，某些节点比其他节点更有影响力。最具影响力的节点是那些其消除会导致网络崩溃的节点，而检测这些节点在许多情况下至关重要。然而，当生物网络规模很大时，这是一项艰巨的任务。在本文中，我们设计并实现了一种高效的并行算法，利用图形处理单元 (GPU) 检测大型生物网络中的有影响力节点。所提出的并行算法背后的基本概念是重新设计几个计算量巨大的检测有影响力节点的程序，并将其转化为相当高效的 GPU 加速原语，如并行排序、扫描和缩减。四个局部指标，包括度中心性 (DC)、伴随行为 (CB)、聚类系数 (CC) 和 H 指数，用于衡量节点影响力。为了评估所提出的并行算法的效率，在实验中采用了五个大型真实生物网络。实验结果表明：(1) 与相应的串行算法相比，所提出的并行算法可以实现大约 48 ∼ 94 的加速比； (2) 与在多核 CPU 上开发的基线并行算法相比，所提出的并行算法对于 DC 和 H-Index 的加速比为 5 ∼ 9，而对于 CB 和 CC 的加速比由于度分布不均匀而略慢；(3) 当使用 DC 和 H-Index 时，所提出的并行算法能够在不到 3 秒的时间内检测出由 1.5 亿条边组成的大型生物网络中的影响节点。© 2019 Elsevier BV 保留所有权利。