公开(公告)号：US20130339290A1

公开(公告)日：2013-12-19

申请号：US13566313

申请日：2012-08-03

申请人： Min Joong LEE ,  Jung Min LEE ,  Jaimie Y. PARK ,  Ryan H. CHOI ,  Chin Wan CHUNG

发明人： Min Joong LEE ,  Jung Min LEE ,  Jaimie Y. PARK ,  Ryan H. CHOI ,  Chin Wan CHUNG

IPC分类号： G06N5/02

CPC分类号： G06F17/10

摘要： The present invention provides a method for updating betweenness centrality of a graph, which obtains the betweenness centrality of an unweighted graph, which is updated when edges are updated, the method comprising the steps of: obtaining a minimum union cycle (an MUC, a subset of edges of the graph in which every vertex of the graph is incident to an even number of edges) of the updated graph; extracting an MUC (i.e., an MUCU) containing a vertex, which is incident to the updated edge, and calculating the betweenness centrality (i.e., local betweenness centrality) due to the shortest paths (internal paths) in the MUCU; obtaining the betweenness centrality (an increase of an external path) due to the shortest paths of the graph, which are not included in the MUCU; and calculating the betweenness centrality of the graph by adding the increase of the external path to the local betweenness centrality.

摘要翻译： 本发明提供了一种用于更新图形的中心性的方法，其获得未加权图的中间性，其在边缘被更新时被更新，所述方法包括以下步骤：获得最小联合周期（MUC，子集 图的边缘，其中图的每个顶点入射到偶数个边缘）; 提取入侵到更新的边缘的包含顶点的MUC（即，MUCU），并计算由于MUCU中的最短路径（内部路径）引起的中间关系（即，局部中心性）; 获得不包括在MUCU中的图形的最短路径的中间性（外部路径的增加）; 并通过将外部路径的增加添加到局部中心性之间来计算图形的中间性。

公开(公告)号：US09075734B2

公开(公告)日：2015-07-07

申请号：US13566313

申请日：2012-08-03

申请人： Min Joong Lee ,  Jung Min Lee ,  Jaimie Y. Park ,  Ryan H. Choi ,  Chin Wan Chung

发明人： Min Joong Lee ,  Jung Min Lee ,  Jaimie Y. Park ,  Ryan H. Choi ,  Chin Wan Chung

IPC分类号： G06F17/10

CPC分类号： G06F17/10

摘要： The present invention provides a method for updating betweenness centrality of a graph, which obtains the betweenness centrality of an unweighted graph, which is updated when edges are updated. First of all, the method is performed by obtaining a minimum union cycle (an MUC) of the updated graph, and extracting an MUC (MUCU) containing a vertex, which is incident to the updated edge. And a first betweenness centrality due to the shortest paths in the MUCU, and a second betweenness centrality due to the shortest paths, not included in the MUCU, are calculated. And finally, a final betweenness centrality of the graph is obtained by adding the first and second betweenness centralities. By using the method, the search space and calculation cost can be remarkably reduced.

摘要翻译： 本发明提供了一种用于更新图形的中心性的方法，其获得未加权图的中间性，当边缘被更新时被更新。 首先，通过获得更新图的最小联合周期（MUC），并且提取包含入更新边缘的顶点的MUC（MUCU）来执行该方法。 并且计算出由MUCU中最短路径引起的第一个中间性以及不包含在MUCU中的由最短路径引起的第二个中间性。 最后，通过添加第一和第二中间集中度来获得图的最终中间性。 通过使用该方法，可以显着降低搜索空间和计算成本。