［本站讯］近日，计算机学院智能计算研究所的研究成果“Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks”被数据库领域顶级学术会议VLDB 2024以长文形式接收。论文第一作者是山东大学助理教授王芯蕊，通讯作者是山东大学教授于东晓，合作者包括山东大学硕士研究生王怡然、上海交通大学教授林学民、香港中文大学教授于旭、浙江师范大学教授高宏和山东大学教授成秀珍，山东大学为第一作者和通讯作者单位。

图1：共享BFS DAG加速cBC计算举例

该研究首次聚焦并深入研究了异构信息网络分析中的一个关键问题：如何定义并高效计算异构图顶点的中介中心性（Betweenness Centrality，BC）。该研究创新性地提出了基于元路径的BC定义框架，并在此框架下给出粗粒度中介中心性（cBC）和细粒度中介中心性（fBC）的形式化度量；提出了一种通用算法，可用于计算cBC、fBC以及更复杂的度量变体。此外，为了进一步提高计算效率，该研究提出了多种优化策略，通过图网络压缩和共享广度优先搜索有向无环图（BFS DAG），来加速cBC和fBC的计算。

图2：不同优化策略对cBC计算的加速效果

图3：不同的优化策略对fBC计算的加速效果

该研究为异构信息网络顶点重要性分析提供了新的视角和工具，能够有效应用于多种领域。例如，在学术网络中，通过比较研究人员在不同时间段内cBC和fBC的排名关系，能够找到学术界的“新星”和跨领域研究人员；在生物代谢网络中，通过寻找cBC与fBC排名高的化合物，能够找到生物代谢网络中的关键中间产物，并且fBC排名更高的化合物所在的代谢途径更不容易受到基因突变的影响。为了验证优化策略对加速cBC和fBC计算的有效性，该研究在多个真实大规模异构信息网络上进行了实验。图2、图3的实验结果表明，多种优化策略对cBC和fBC计算有明显的加速效果，特别是在DBLP数据集上，与基础算法相比，优化策略能够将cBC的计算时间从20小时降至0.5小时，将fBC的计算时间从38.75小时降至0.57小时。

VLDB会议全称为International Conference on Very Large Data Bases，是数据库领域历史悠久的三大顶级会议（SIGMOD、VLDB、ICDE）之一，每届会议集中展示当前数据库研究的前沿方向，包括数据库系统、数据管理、数据挖掘等，VLDB会议是中国计算机学会推荐的A类国际会议。