Un réseau de relaxation lagrangienne pour le rapprochement de graphes

Un réseau de relaxation lagrangienne pour le rapprochement de graphes est présenté. Le problème est formulé comme suit : étant donné les graphes G et g, trouver une matrice de permutation M qui met en correspondance les deux ensembles de sommets. Les contraintes de matrice de permutation sont formulées dans le cadre du recuit déterministe. Notre approche est dans le même esprit qu'une approche de décomposition lagrangienne en ce sens que les contraintes de ligne et de colonne sont satisfaites séparément avec un multiplicateur de Lagrange utilisé pour égaler les deux "solutions". En raison des symétries inévitables dans l'isomorphisme des graphes (résultant en plusieurs minima globaux), nous ajoutons un terme d'auto-amplification brisant la symétrie afin d'obtenir une matrice de permutation. Avec l'application d'une transformation algébrique préservant le point fixe à la fois à la mesure de distance et aux termes d'auto-amplification, nous obtenons un réseau de relaxation lagrangienne. Le réseau effectue une minimisation par rapport aux paramètres de Lagrange et une maximisation par rapport aux variables de la matrice de permutation. Des résultats de simulation sont présentés sur des graphes aléatoires à 100 nœuds et pour une large gamme de connectivités.