The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jul. 07, 2015
Filed:
Aug. 03, 2012
Min Joong Lee, Daejeon, KR;
Jung Min Lee, Daejeon, KR;
Jaimie Y. Park, Daejeon, KR;
Ryan H. Choi, Daejeon, KR;
Chin Wan Chung, Daejeon, KR;
Min Joong Lee, Daejeon, KR;
Jung Min Lee, Daejeon, KR;
Jaimie Y. Park, Daejeon, KR;
Ryan H. Choi, Daejeon, KR;
Chin Wan Chung, Daejeon, KR;
Korean Advanced Institute of Science and Technology, Daejeon, KR;
Abstract
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.