NetworkX：間違った重み付きグラフの近似/不正確な部分グラフ同型図

Question

2つのグラフ（AとB）が与えられたとき、エッジ重みの差に基づいてAに一致するBの部分グラフが存在するかどうかを調べようとしています。つまり、関連するエッジの各ペアの差の合計をとると、指定されたしきい値を下回ります。頂点のラベルはAとBの間で一貫していないので、私はエッジの重さに頼っています。

Aは多少小さく（たとえば最大10）、Bは大きく（たとえば最大200）です。

Answer 1

Iは、これら2つのパッケージのいずれかを助けることができると信じて：

MATLABツールボックスにマッチンググラフが「任意クロネッカーbistochastic正規化して、アフィン制約（SMAC）とスペクトルグラフマッチングを実現します」。これは、それがMATLABツールボックスマッチンググラフに使用されるアルゴリズムはTimotheeクール、Praveenさんスリニバサンによる論文に記載されたアルゴリズムに基づいている http://www.timotheecour.com/software/graph_matching/graph_matching.html

「異なるサイズのグラフ（部分グラフマッチング）を処理する」ウェブページ上に述べJianbo ShiはBalanced Graph Matchingと題した。この論文はNIPS 2006で公開されました。エラー許容グラフのマッチングをサポートしているため、エラー許容サブグラフマッチングをサポートしているように見えるグラフマッチングツールキット（GMT）という2番目のツールキットがあります。 。スペクトル法を使うのではなく、編集距離を計算する方法がいろいろありますし、最小編集距離のargmaxを与えることで最良の一致を見つけることができました。サブグラフマッチングを明示的にサポートしておらず、効率性を気にしない場合は、Bのすべてのサブグラフを検索し、GMTを使用してAのサブグラフの一致を見つけようとするかもしれません。残念なことにこれらはいずれもPythonでは見えず、networkxのグラフ形式もサポートしていないようです。しかし、私はあなたがnetworkxグラフの表現をこれらのツールキットで使えるものに変えるコンバータを見つけることができると信じています。次に、ツールキットを実行して、必要な部分グラフマッチングを出力できます。