電子情報通信学会ソサイエティ大会講演要旨
N-1-21
重み付き無向グラフの媒介中心性の更新式
◎難波俊行・高橋規一(岡山大)
媒介中心性はグラフ内の各頂点の重要度を表す指標の一つである.媒介中心性の効率的計算法としてBrandesのアルゴリズムが広く利用されているが,グラフの構造が変化した場合には最初から計算を行わねばならないという問題がある.そこで著者らはグラフに辺が挿入された後の各頂点の媒介中心性を,挿入前の最短経路の長さと個数から求める方法を与えた.本研究では,その結果の拡張として,重み付きグラフに辺や頂点が追加されたときの媒介中心性の更新式を与える.