METHOD FOR UPDATING BETWEENNESS CENTRALITY OF GRAPH

摘要

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 MUC_U) 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 MUC_U; obtaining the betweenness centrality (an increase of an external path) due to the shortest paths of the graph, which are not included in the MUC_U; and calculating the betweenness centrality of the graph by adding the increase of the external path to the local betweenness centrality.