课题组博士生赵琛一篇论文被IEEE INFOCOM 2023接收

课题组题为：Galliot: Path Merging Based Betweenness Centrality Algorithm on GPU 论文被IEEE INFOCOM 2023成功接受。

IEEE INFOCOM，全称为IEEE International Conference on Computer Communications是IEEE组织在通信网络领域的旗舰性会议，也是CCF类推荐的A类会议。IEEE INFOCOM 2023将于2023年5月17至20日在美国纽约举办。本届INFOCOM会议收到了1312篇有效投稿，其中252篇被大会接受，录用率为19.2%。

顶点中心度作为顶点重要性衡量中最为基础的一种方法，已经被广泛应用于多种场景。介数中心度采用通过顶点的最短路径的数量与全局最短路径数量的比例来衡量顶点的重要程度，能够很好地反映图中的路径信息和顶点对全局的重要性，兼顾了图结构局部和整体的信息。传统的介数中心度计算过程中由于需要多次遍历图结构，存在一定程度的冗余计算。并且计算过程中需要多个临时数组来存储中间变量，导致内存膨胀的问题，这对于板载内存空间受限的GPU而言是一个重要挑战。

本论文针对介数中心度计算过程中存在的内存膨胀和冗余计算的问题。提出了一种基于路径合并的介数中心度计算方法Galliot，通过对计算过程中的局部最短路径合并，从而实现对计算的剪枝。同时算法设计了一种面向局部内存的活跃队列维护和更新技术，将多个活跃队列合并成一个，有效降低了介数中心度计算过程中的内存消耗问题。论文基于NVIDIA GPU设计了一系列实验来验证本文所提出的 Galliot算法的性能。实验结果表明，相比于当前主流的介数中心度计算方法，Galliot在相同GPU上可以处理的图数据的顶点数和边数分别是当前主流算法可以处理的最大图数据的 11.32和 5.67倍，同时 Galliot 相比于主流的介数中心度计算算法可以获得高达 38.77倍速度提升。

                        图1 路径合并示例

                        图2 顶点更新内存load 操作数对比

                        图3 相同数据集上的性能对比

作者介绍：

郑志高，武汉大学计算机学院，博士后，主要从事大数据、并行与分布式系统方面的研究。

赵琛 ，武汉大学计算机学院，博士，主要从事图计算，并行与分布式系统方面的研究。

谢沛辰，武汉大学计算机学院，硕士，主要从事软件工程、图学习和大数据方面的研究。

杜博，武汉大学计算机学院院长，教授。国家自然科学基金杰出青年、优秀青年科学基金获得者，主要致力于医学人工智能、图像处理与计算机视觉、模式识别、机器学习等研究工作，发表了多篇具有影响力的高水平论文，具备丰富的科研和项目实践经验。

[1]“Galliot: Path Merging Based Betweenness Centrality Algorithm on GPU”, in IEEE INFOCOM, NY, USA, 2023.