| Presentation | 2016-09-15 A Fast Method for Finding the Edge to be Inserted to Minimize Betweenness Centrality of a Specified Vertex Toshiyuki Namba, Tatsuki Kohno, Norikazu Takahashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Betweenness centrality is a measure that represents the importance of each vertex of 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. A simple way to increase the robustness of a given graph is to insert a small number of edges so that the largest betweenness centrality decreases as much as possible. In this paper, we consider the problem of finding an edge to be inserted in order to minimize the betweenness centrality of a specified vertex of a given graph. We first analyze theoretically how the number and length of the shortest paths between any pair of two vertices are affected by an edge insertion. We then design a fast algorithm for solving the problem mentioned above, by using the theoretical results. We finally examine the efficiency of the proposed algorithm by some experiments on random graphs and scale-free graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | complex network / betweenness centrality / robustness / edge insertion |
| Paper # | NLP2016-56 |
| Date of Issue | 2016-09-07 (NLP) |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2016/9/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Konan Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hisato Fujisaka(Hiroshima City Univ.) |
| Vice Chair | Masaharu Adachi(Tokyo Denki Univ.) |
| Secretary | Masaharu Adachi(Konan Univ.) |
| Assistant | Hiroyuki Asahara(Okayama Univ. of Science) / Toshihiro Tachibana(Shonan Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Nonlinear Problems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fast Method for Finding the Edge to be Inserted to Minimize Betweenness Centrality of a Specified Vertex |
| Sub Title (in English) | |
| Keyword(1) | complex network |
| Keyword(2) | betweenness centrality |
| Keyword(3) | robustness |
| Keyword(4) | edge insertion |
| 1st Author's Name | Toshiyuki Namba |
| 1st Author's Affiliation | Okayama University(Okayama Univ.) |
| 2nd Author's Name | Tatsuki Kohno |
| 2nd Author's Affiliation | Okayama University(Okayama Univ.) |
| 3rd Author's Name | Norikazu Takahashi |
| 3rd Author's Affiliation | Okayama University(Okayama Univ.) |
| Date | 2016-09-15 |
| Paper # | NLP2016-56 |
| Volume (vol) | vol.116 |
| Number (no) | NLP-215 |
| Page | pp.pp.63-68(NLP), |
| #Pages | 6 |
| Date of Issue | 2016-09-07 (NLP) |