講演情報
[B-16-17]粗視化グラフ上での古典的グラフアルゴリズムの解近似精度に関する一検討
◎△柿原 悠人1、大崎 博之1 (1. 関西学院大学)
キーワード：
グラフ粗視化、最短経路、ページランク、最小カット
近年、ネットワーク解析の対象となるグラフの規模は拡大しており、数百万ノードに達することも珍しくない。そのため、最短経路探索、中心性計算、カット最適化といった古典的なグラフアルゴリズムを元の規模のまま実行することは、計算量およびメモリ消費の観点から困難になりつつある。このような背景から、元グラフを縮約して計算負荷を削減する前処理として、グラフ粗視化が広く用いられている。グラフ粗視化は、隣接するノードをまとめて代表ノードへ集約することでグラフの規模を縮小し、縮約された小さなグラフ上での解析を可能にする。しかし、グラフ粗視化の有効性を裏付ける既存評価の多くは、スペクトルの保存や埋め込み品質、学習精度といった代理指標に依存している。そのため、粗視化されたグラフ上で古典的なアルゴリズムを直接実行した際に、元グラフの解をどの程度近似できるかは我々の知る限り体系的に検証されていない。グラフの構造が保存されても、組合せ論的な解が保存される保証はないからである。本研究では、この課題に対処するため、最短経路探索、PageRank、最小カットの3つの主要なアルゴリズムを対象とする。これらを代表的な粗視化手法によって縮約された合成グラフ上で直接実行し、元グラフの解に対する近似誤差を体系的に測定することを目的とする。