時々刻々と成長するグラフのための中心性モニタリング

概要

論文の詳細を見る
本論文では時々刻々とノードの数を増やしながら成長するグラフの中から,他のノードまでの距離の和が最小になるノード(最も距離中心性の高いノード)と他のノードまでの距離の最大値が最も小さくなるノード(最も離心中心性の高いノード)を効率的かつ正確に検出し続ける問題を対象とする.過去のこの問題に対する手法では最も中心性の高いノードを高速に求めることができる代わりに計算結果の正確性を犠牲にしていた.本論文は正確性を犠牲にしないで最も中心性の高いノードを求めることができないかということを動機にしている.提案手法は(1)解の正確性を保ったまま元のグラフを縮退してグラフの近似を行い,その近似グラフにおける中心性の値を計算し,(2)中心性を求めるときに不必要な計算を早期に打ち止めるという2つのアプローチで構成される.これらのアプローチにより数多くのノードを枝刈りできるために効率的な検出が可能になる.理論的解析により提案手法は検出結果が正確であり,また必要となる計算量は従来の手法より少ないオーダとなることが分かった.数十万ノードを含む実データで検証を行ったところ,提案手法は解の正確性を保証したまま従来手法と比較して非常に高速であることが確認された.
2011-04-15

時々刻々と成長するグラフのための中心性モニタリング

スポンサーリンク

概要

著者

関連論文

スポンサーリンク