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

IPSJ

Bibliographic Information

Other Title
  • Connectedness Centrality Robust to Link Cutting Equipped with its Fast Computation Method

Search this article

Abstract

本論文では，リンク切断が発生する状況下でも，孤立したノードまたは小さな連結成分となりにくく，つねに多くのノードに到達可能なノードを抽出するために，連結中心性と呼ぶ新たな中心性指標を提案する．リンク切断は確率的な事象であり，考えられる切断リンクの組合せ数は膨大であり，各ノードの連結中心性スコアを厳密に計算しようとすると，多大な時間計算量が必要となるため，大規模ネットワークへの適用は困難になる．そこで，すべてを孤立ノードとした初期状態から1本ずつリンクを追加した際の差分値だけを計算することで，高速に連結中心性スコアを求めるアルゴリズムを提案する．現実の道路ネットワークを用いた実験により，近似計算の精度と頑健性について評価する．

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.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top