文献

J-GLOBAL ID：201802262358584581   整理番号：18A1776933

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

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

著者 (4件)： 伏見卓恭 (東京工科大 コンピュータサイエンス) ,  斉藤和巳 (神奈川大 理) ,  池田哲夫 (静岡県大 経営情報) ,  風間一洋 (和歌山大 システム工)
資料名： 情報処理学会論文誌トランザクション 数理モデル化と応用(Web)  (情報処理学会論文誌 数理モデル化と応用(Web))
巻： 11  号： 2  ページ： 1-11 (WEB ONLY)  発行年： 2018年07月26日 
JST資料番号： U0475A  ISSN： 1882-7780  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *道路網 ,  *リンク ,  *指標 ,  度 ,  *高速計算 ,  節点 ,  計算量 ,  アルゴリズム ,  ロバスト性
準シソーラス用語： 近似計算 ,  計算アルゴリズム ,  中間中心性 ,  *連結中心性

分類 (2件)： 計算理論  (JB02000A) ,  道路工学一般  (RC08010M)

引用文献 (23件)：

• Crucitti, P., Latora, V. and Porta, S.: Centrality Measures in Spatial Networks of Urban Streets, Physical Review E, Vol.73, No.3, p.036125+ (2006).
• Montis, D.A., Barthelemy, M., Chessa, A. and Vespignani, A.: The Structure of Interurban Traffic: A Weighted Network Analysis, Environment and Planning B: Planning and Design, Vol.34, No.5, pp.905-924 (2007).
• Park, K. and Yilmaz, A.: A Social Network Analysis Approach to Analyze Road Networks, Proc. ASPRS Annual Conference 2010 (2010).
• 伏見卓恭,斉藤和巳,武藤伸明,池田哲夫,風間一洋:実距離を考慮した中心性指標の提案と重要観光スポット抽出への応用,人工知能学会論文誌,Vol.30, No.6, pp.703-712 (2015).
• Seidman, S.B.: Network structure and minimum degree, Social Networks, Vol.5, No.3, pp.269-287 (1983).

タイトルに関連する用語 (2件)： リンク ,  計算法