304am永利集团官网计算机学院智能计算研究所的研究成果“Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks”被数据库领域顶级学术会议VLDB 2024以长文形式接收。论文第一作者是304am永利集团官网助理教授王芯蕊,通讯作者是304am永利集团官网教授于东晓,合作者包括304am永利集团官网硕士研究生王怡然、上海交通大学教授林学民、香港中文大学教授于旭、浙江师范大学教授高宏和304am永利集团官网教授成秀珍,304am永利集团官网为第一作者和通讯作者单位。
该研究首次聚焦并深入研究了异构信息网络分析中的一个关键问题:如何定义并高效计算异构图顶点的中介中心性(Betweenness Centrality,BC)。该研究创新性地提出了基于元路径的BC定义框架,并在此框架下给出粗粒度中介中心性(cBC)和细粒度中介中心性(fBC)的形式化度量。随后,该研究提出了一种通用算法,可用于计算cBC、fBC以及更复杂的度量变体。此外,为了进一步提高计算效率,该研究提出了多种优化策略,通过图网络压缩和共享广度优先搜索有向无环图(BFS DAG),来加速cBC和fBC的计算。
图1 共享BFS DAG加速cBC计算举例
该研究为异构信息网络顶点重要性分析提供了新的视角和工具,能够有效应用于多种领域。例如,在学术网络中,通过比较研究人员在不同时间段内cBC和fBC的排名关系,能够找到学术界的“新星”和跨领域研究人员;在生物代谢网络中,通过寻找cBC与fBC排名高的化合物,能够找到生物代谢网络中的关键中间产物,并且fBC排名更高的化合物所在的代谢途径更不容易受到基因突变的影响。为了验证优化策略对加速cBC和fBC计算的有效性,该研究在多个真实大规模异构信息网络上进行了实验。图2、图3的实验结果表明,多种优化策略对cBC和fBC计算有明显的加速效果,特别是在DBLP数据集上,与基础算法相比,优化策略能够将cBC的计算时间从20小时降至0.5小时,将fBC的计算时间从38.75小时降至0.57小时。
图2 不同优化策略对cBC计算的加速效果
图3 不同的优化策略对fBC计算的加速效果
VLDB会议全称为International Conference on Very Large Data Bases,是数据库领域历史悠久的三大顶级会议(SIGMOD、VLDB、ICDE)之一,每届会议集中展示当前数据库研究的前沿方向,包括数据库系统、数据管理、数据挖掘等,VLDB会议是中国计算机学会推荐的A类国际会议。
(文:王怡然、王芯蕊 审核:于东晓 责任编辑:宋曙光、李雅洁 供稿单位:304am永利集团官网)