フシミ　タカヤス   Takayasu Fushimi   伏見　卓恭    所属   コンピュータサイエンス学部 コンピュータサイエンス学科    職種   専任講師
言語種別	日本語
発行・発表の年月	2018/07
形態種別	学術論文
査読	査読あり
標題	リンク切断に頑健な連結中心性とその高速計算法
執筆形態	共著
掲載誌名	情報処理学会論文誌 数理モデル化と応用
掲載区分	国内
巻・号・頁	11(2),1-11頁
著者・共著者	伏見 卓恭，斉藤 和巳，池田 哲夫，風間 一洋
概要	In this paper, in order to extract nodes that do not become isolated nodes but have many nodes that can be reached along with the link even in the situation where link cutting occurs, we propose a new centrality measure called connectedness centrality. Since link cuttings are probabilistic and the number of combinations of which links are cut is enormous, a great amount of computation time is required, when we strictly calculate the connected centrality score of each node. Therefore, we propose an efficient algorithm based on simulations where we add all the links one by one from the initial state where all nodes are isolated ones. In each simulation, by calculating the scores of a few representative nodes and holding only the difference value between each node and its representative node, we compute the connectedness centrality score quickly. By our experiments using real road networks, we evaluate the robustness and approximation accuracy of our proposed algorithm.