Korea Advanced Institute of Science and Technology

Min Joong Lee

Jung Min Lee

Ryan H Choi

Jaimie Y Park

Chin Wan Chung

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 (MUC) containing a vertex, which is incident to the updated edge. And a first betweenness centrality due to the shortest paths in the MUC, and a second betweenness centrality due to the shortest paths, not included in the MUC, 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.

Growing community of inventors

Daejeon, South Korea

Min Joong Lee