情報処理学会 第88回全国大会

2N-01
ネットワークにおける改訂版マイヤーソン中心性について
○神田彗佑,山田敏規(埼玉大)
協力ゲーム理論に基づくマイヤーソン中心性は、グラフの連結性を提携の価値と見なす指標である。しかし最短パスを用いた従来の定義では、閉路を含むグラフにおいてマイヤーソン値の公理を満たさない場合がある。本稿では、まず全単純パスを用いることで同公理を満たす「改訂版マイヤーソン中心性」を提案する。しかし、この手法は計算量が指数的に増大する課題がある。そこで、パス長に上限を設ける「パス長制限マイヤーソン中心性」を提案する。本手法は同公理を満たしつつ、計算量を多項式時間に抑制可能である。また提案手法の定式化に加え、既存手法との比較実験による有効性の検証を行う。