著者

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

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.96, no.5, pp.1158-1165, 2013-05-01

---

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