グラフの類似性を評価する - ryamadaの遺伝学・遺伝統計学メモ

はじめに 参考PDF グラフの同形性評価(graph isomorphism)と類似性評価 Graph isomorphismはグラフ構成要素であるノードの1対1対応とエッジの1対1対応によって定義されている。それに対して、類似性評価は同形性からのはずれの程度の評価であり、その尺度は定義に依存する グラフの類似度評価 評価の指標(グラフ間距離)に求められるもの Metric 同一グラフ間距離は0 グラフＡからグラフＢへの距離とグラフＢからグラフＡへの距離は同一(対象性 Symmetry) グラフＡからＢへの距離とグラフＢからＣへの距離の和はグラフＡからＣへの距離を越えない(Triangle inequality) 評価方法 Graph edit distance法 ２つのグラフを比較し、グラフに操作(ノードおよびエッジの削除・挿入・置換)を加えることで、両グラフを同一にするときに、その最小

[junzou]

最大サブグラフを用いたグラフの類似性の評価の説明