Summary
International Symposium on Nonlinear Theory and Its Applications
2016
Session Number:C1L-E
Session:
Number:C1L-E-5
A Fast Method for Finding the Edge to Be Added to Minimize Betweenness Centrality of a Specified Vertex
Toshiyuki Namba, Tatsuki Kohno, Norikazu Takahashi,
pp.-
Publication Date:2016/11/27
Online ISSN:2188-5079
Summary:
Betweenness centrality is a measure that represents the importance of each vertex in a graph. From the viewpoint of the robustness against attacks and failures, it is desired that all vertices take similar values of the betweenness centrality. In this paper, a fast algorithm for finding the edge to be added to minimize the betweenness centrality of a specified vertex is developed. The efficiency of the proposed algorithm is confirmed by some experiments on random graphs and scale-free graphs. It is also shown experimentally that the proposed algorithm is useful for improving the robustness of the graph by an edge addition.