公开(公告)号：KR101329350B1

公开(公告)日：2013-11-14

申请号：KR1020120064528

申请日：2012-06-15

Applicant: 한국과학기술원

Inventor： 이민중 ,  이정민 ,  박예진 ,  최현 ,  정진완

IPC: G06F17/00 ,  G06F17/10

CPC classification number: G06F17/10

Abstract: The present invention relates to a betweenness centrality updating method of a graph. The method comprises (a) a step of obtaining a minimum cycle (hereinafter called the MUC) from an updated graph; (b) a step of extracting the MUC including a peak (hereinafter called the updated peak) transmitted to an updated edge (hereinafter called the MUCU) and calculating betweenness centrality (hereinafter called the local betweenness centrality) due to the shortest paths (hereinafter called the inner path) within the MUCU; (c) a step of obtaining betweenness centrality (hereinafter called the outer path increment) due to the shortest paths (hereinafter called the outer path) of the graph which is not included within the MUCU; and (d) a step of calculating betweenness centrality (hereinafter called the global betweenness centrality) of the graph by adding the outer path increament to the local betweenness centrality.

Abstract translation: 本发明涉及图形的中间性中心更新方法。 该方法包括（a）从更新的图形获得最小周期（以下称为MUC）的步骤; （b）提取MUC的步骤，包括发送到更新边缘的峰值（以下称为更新的峰值）（以下称为MUCU），并计算由于最短路径而导致的中心性（以下称为局部中心性） 内部路径）在MUCU内; （c）由于不包含在MUCU内的图形的最短路径（以下称为外部路径）而获得间隔中心性（以下称为外部路径增量）的步骤; 和（d）通过加上与局部中心性之间的外在路径来计算图的中心性（以下称为全局中心性）之间的步骤。