计算机应用

作者：刘震宇, 王朝坤, 郭高扬

单位：清华大学 软件学院，北京 100084

关键词：介数中心度,动态网络,最短距离,并行算法,社区结构

基金：国家自然科学基金资助项目(61872207)

介数中心度是评价图中节点重要性的一项常用指标，然而在大规模动态图中介数中心度的更新效率很难满足应用需求。随着多核技术的发展，算法并行化已成为解决该问题的有效手段之一。因此，提出一种面向动态网络的介数中心度并行算法（PAB）。首先，通过社区过滤、等距剪枝和分类筛选等操作减少了冗余点对的时间开销；然后，基于对算法确定性的分析和处理实现了并行化。在真实数据集和合成数据集上进行了对比实验，结果显示在添加边更新时PAB的更新效率为并行算法中最新的batch-iCENTRAL的4倍。可见，所提算法能够有效提高动态网络中介数中心度的更新效率。

来源：2023年第7期

《计算机应用》期刊编辑部

查看计算机应用杂志2023年第7期