抄録

D-020
固有値を用いたグラフ検索のためのグラフの行列表現の比較

近年、図形やたんぱく質、DNA、化合物などがグラフで表現されており，グラフは複雑な構造を表すための重要なデータモデルとなっている。あるグラフに他のグラフが含まれるかどうかを判定する問題は部分グラフ同型性判定問題と呼ばれ、グラフマイニングや化合物のデータベース、パターン認識などに応用される。グラフを行列で表現し、その固有値を比較することによって部分グラフでないものを見つけることができる。我々はグラフの行列表現を変えるとその固有値が変化することに着目し、行列表現によって判定精度や処理時間がどのように変化するのかについて実験的に比較した。