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

摘要

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