| 时态图顶点介数中心度计算方法 |
| |
| 引用本文： | 张天明,赵杰,金露,陈璐,曹斌,范菁.时态图顶点介数中心度计算方法[J].计算机研究与发展,2023(10):2383-2393. |
| |
| 作者姓名： | 张天明 赵杰 金露 陈璐 曹斌 范菁 |
| |
| 作者单位： | 1. 浙江工业大学计算机科学与技术学院;2. 浙江大学计算机科学与技术学院 |
| |
| 基金项目： | 浙江省自然科学基金项目（LQ22F020018）；;浙江省重点研发项目（2023C01048）~~； |
| |
| 摘 要： | 在社会网络分析中，介数中心度用于衡量顶点对网络结构的贡献大小，是一种广泛使用的顶点重要度衡量指标.该指标主要通过计算经过顶点的最短路径数来表明顶点的重要性.目前研究的介数中心度算法主要聚焦在普通图上，针对时态图的研究工作较少.普通图介数中心度计算方法主要依据Brandes算法设计，Brandes算法有效的关键理论是最短路径的子路径依然是最短路径，即最优子结构特性.然而时态图包含时态信息，时态路径类型多样，并且时态最短路径并不满足此特性，因此普通图介数中心度计算理论与方法不再适用于时态图.鉴于此，定义了严格（时态递增）和非严格（时态非递减）2种时态路径类型，并研究了时态图介数中心度计算理论与方法.提出了一种高效的基于消息传播的2阶段迭代计算框架.第1阶段采用自顶向下的广度优先遍历方式计算时态最短路径；第2阶段采用自底向上的方式计算顶点的后继节点和孩子节点对其介数中心度的贡献值，并设计了基于消息传播机制的迭代累积计算方法.为了提高效率和可扩展性，实现了基于OpenMP(open multiprocessing)框架的多线程并行算法FTBC(fast temporal betweenness...
|
| 关 键 词： | 时态图 介数中心度 时态路径 并行处理 图算法 |
|
|
