时态图顶点介数中心度计算方法

摘要：

在社会网络分析中,介数中心度用于衡量顶点对网络结构的贡献大小,是一种广泛使用的顶点重要度衡量指标.该指标主要通过计算经过顶点的最短路径数来表明顶点的重要性.目前研究的介数中心度算法主要聚焦在普通图上,针对时态图的研究工作较少.普通图介数中心度计算方法主要依据Brandes算法设计,Brandes算法有效的关键理论是最短路径的子路径依然是最短路径,即最优子结构特性.然而时态图包含时态信息,时态路径类型多样,并且时态最短路径并不满足此特性,因此普通图介数中心度计算理论与方法不再适用于时态图.鉴于此,定义了严格(时态递增)和非严格(时态非递减)2种时态路径类型,并研究了时态图介数中心度计算理论与方法.提出了 一种高效的基于消息传播的2阶段迭代计算框架.第1阶段采用自顶向下的广度优先遍历方式计算时态最短路径;第2阶段采用自底向上的方式计算顶点的后继节点和孩子节点对其介数中心度的贡献值,并设计了基于消息传播机制的迭代累积计算方法.为了提高效率和可扩展性,实现了基于OpenMP(open multiprocessing)框架的多线程并行算法FTBC(fast temporal betweenness centrality).基于8个真实的时态图数据集实验结果表明,与现有方法相比,提出的介数中心度计算方法具有更优的计算性能.

关键词：时态图、介数中心度、时态路径、并行处理、图算法

所属期刊栏目：60

分类号：TP311.131(计算技术、计算机技术)

在线出版日期：2023-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：2383-2393