公开(公告)号：CN113961574A

公开(公告)日：2022-01-21

申请号：CN202111219145.7

申请日：2021-10-20

Applicant: 中电积至(海南)信息技术有限公司

Inventor： 郑超 ,  陆秋文 ,  郑植效 ,  吴锐忠

IPC: G06F16/23 ,  G06F9/50

Abstract: 本发明提供一种在图数据库更新时快速计算Betweenness Centrality的方法。所述在图数据库更新时快速计算Betweenness Centrality的方法，包括以下操作步骤：S1、寻找原始图中的最大联合环MUC；S2、当图更新(增边、删边)时，开始更新图中的最大联合环MUC。本发明提供一种在图数据库更新时快速计算Betweenness Centrality的方法，相较于现有的算法，本方法在思路上充分利用了图更新时，Betweenness Centrality发生改变的部分(各个MUC集合)、不发生改变的部分，图更新时仅仅用昂贵的Brandes算法计算各个MUC集合内顶点的局部Betweenness Centrality，在此基础上，对于还没考虑到的顶点对使用简单的附加计算，就能得出MUC中各顶点精确(全局)Betweenness Centrality，从而缩小了昂贵的重新计算Betweenness Centrality大小的顶点数量与范围，从而加快了计算时间。