リンク切断に頑健な連結中心性とその高速計算法

• Item type: Trans(1)
• 公開日: 2018-07-26
• タイトル: リンク切断に頑健な連結中心性とその高速計算法
• タイトル / 言語: en
• タイトル: Connectedness Centrality Robust to Link Cutting Equipped with its Fast Computation Method
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] リンク切断モデル，中心性指標，頑健性，シミュレーション
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京工科大学コンピュータサイエンス学部
• 著者所属: 神奈川大学理学部
• 著者所属: 静岡県立大学経営情報学部
• 著者所属: 和歌山大学システム工学部
• 著者所属(英): en
• 著者所属(英): School of Computer Science, Tokyo University of Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Science, Kanagawa University
• 著者所属(英): en
• 著者所属(英): School of Management and Information, University of Shizuoka
• 著者所属(英): en
• 著者所属(英): Faculty of Systems Engineering, Wakayama University
• 著者名: 伏見, 卓恭; 斉藤, 和巳; 池田, 哲夫; 風間, 一洋
• 著者名(英): Takayasu, Fushimi; Kazumi, Saito; Tetsuo, Ikeda; Kazuhiro, Kazama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，リンク切断が発生する状況下でも，孤立したノードまたは小さな連結成分となりにくく，つねに多くのノードに到達可能なノードを抽出するために，連結中心性と呼ぶ新たな中心性指標を提案する．リンク切断は確率的な事象であり，考えられる切断リンクの組合せ数は膨大であり，各ノードの連結中心性スコアを厳密に計算しようとすると，多大な時間計算量が必要となるため，大規模ネットワークへの適用は困難になる．そこで，すべてを孤立ノードとした初期状態から1本ずつリンクを追加した際の差分値だけを計算することで，高速に連結中心性スコアを求めるアルゴリズムを提案する．現実の道路ネットワークを用いた実験により，近似計算の精度と頑健性について評価する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, in order to extract nodes that do not become isolated nodes but have many nodes that can be reached along 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 cutted 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 11, 号 2, p. 1-11, 発行日 2018-07-26
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会