ノード群の協調的振舞いに着目した集合媒介中心性の提案と応用

伏見 卓恭  斉藤 和巳  池田 哲夫  武藤 伸明  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.5   pp.1158-1165
発行日: 2013/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: ネットワークコミュニティ分析
キーワード: 
媒介中心性,  ノード集合,  ネットワーク構造,  看板配置問題,  

本文: PDF(873.2KB)>>
論文を購入




あらまし: 
社会ネットワーク分析の分野で重要ノードを抽出する指標として中心性指標が提案されており,これらはノードの独立的な性質により,各ノードをランキングする手法である.本論文では,集合内での各ノードの協調的振舞いを想定して,任意のノード群に対する指標として拡張した集合中心性を提案する.集合中心性は,集合内で各ノードが互いに影響し合う点を考慮し,集合としての中心性値が高くなるようなノード集合を抽出する.集合次数中心性を求める問題はK-vertex covering問題に帰着し,集合近接中心性を求める問題はK-median問題に帰着できることを示す.集合媒介中心性においてK 個の重要ノードを選定する問題は,看板配置問題という新たな数理問題の一解法であることを示す.更に,集合媒介中心性を効率的に求めるアルゴリズムを提案する.複数の構造の異なるネットワークを対象とした評価実験より,道路網上への看板配置問題への応用が期待できることを示す.