NetworkX: isomorphisme sous-graphique approximatif/inexact pour les graphiques pondérés non dirigés

Question

Étant donné deux graphiques (A et B), j'essaie de déterminer s'il existe un sous-graphe de B qui correspond à un certain seuil basé sur la différence de poids de bord. C'est-à-dire que si je prends la somme de la différence entre chaque paire d'arêtes associées, elle sera inférieure à un seuil spécifié. Les étiquettes de sommet ne sont pas cohérentes entre A et B, donc je me fie uniquement aux poids de bord.

A sera un peu petit (par exemple au maximum 10) et B sera plus grand (par exemple au maximum 200).

Answer 1

Je crois que l'un de ces deux paquets peuvent aider:

Le graphique assortis Boîte à outils MATLAB « implémente correspondant graphe spectral avec la contrainte affines (SMAC), éventuellement avec Kronecker normalisation bistochastic ». Il indique sur la page Web qu'il « gère des graphiques de différentes tailles (correspondant de sous-graphe) » http://www.timotheecour.com/software/graph_matching/graph_matching.html

L'algorithme utilisé dans le graphique Matching Boîte à outils MATLAB est basé sur l'algorithme décrit dans le document par Timothee Cour, Praveen Srinivasan, et Jianbo Shi intitulé Balanced Graph Matching. L'article a également été publié dans NIPS 2006.

De plus, il existe une deuxième boîte à outils appelée Graph Matching Toolkit (GMT) qui semble prendre en charge la correspondance de sous-graphe tolérante aux erreurs, car elle prend en charge la correspondance de graphes tolérants aux erreurs. . Plutôt que d'utiliser une méthode spectrale, il existe différentes méthodes de calcul de la distance d'édition, et j'ai alors l'impression qu'il trouve la meilleure correspondance en donnant l'argmax de la distance d'édition minimale. Si elle ne prend pas explicitement en charge l'appariement des sous-graphes et que vous ne vous souciez pas de l'efficacité, vous pouvez simplement rechercher tous les sous-graphes de B et utiliser GMT pour rechercher les correspondances de ces sous-graphes dans A. Ou peut-être rechercher un sous-ensemble Les sous-graphes de B. http://www.fhnw.ch/wirtschaft/iwi/gmt

Malheureusement, aucun de ceux-ci ne semble être en format Python, et ils ne semblent pas non plus supporter le format graphique de networkx. Mais je crois que vous pourrez peut-être trouver un convertisseur qui va changer la représentation du réseaux en quelque chose d'utilisable par ces boîtes à outils. Vous pouvez ensuite exécuter les toolkits et générer les correspondances de sous-graphe souhaitées.