distancia de edición del gráfico

En matemáticas e informática , la distancia de edición de grafos ( GED ) es una medida de similitud (o disimilitud) entre dos grafos . El concepto de distancia de edición de grafos fue formalizado matemáticamente por primera vez por Alberto Sanfeliu y King-Sun Fu en 1983. ^{[ 1 ]} Una aplicación importante de la distancia de edición de grafos es la comparación inexacta de grafos , como el reconocimiento de patrones tolerante a errores en el aprendizaje automático . ^{[ 2 ]}

La distancia de edición de grafos entre dos grafos está relacionada con la distancia de edición de cadenas entre cadenas . Con la interpretación de las cadenas como grafos acíclicos dirigidos y conexos de grado máximo uno, las definiciones clásicas de distancia de edición, como la distancia de Levenshtein , ^{[ 3 ] [ 4 ]} la distancia de Hamming ^{[ 5 ]} y la distancia de Jaro-Winkler, pueden interpretarse como distancias de edición de grafos entre grafos adecuadamente restringidos. Asimismo, la distancia de edición de grafos es también una generalización de la distancia de edición de árboles entre árboles con raíz . ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]}

La definición matemática de la distancia de edición de grafos depende de las definiciones de los grafos sobre los que se define, es decir, si los vértices y las aristas del grafo están etiquetados y cómo lo están, y si las aristas son dirigidas . Generalmente, dado un conjunto de operaciones de edición de grafos (también conocidas como operaciones elementales de grafos ), la distancia de edición de grafos entre dos grafos${\displaystyle g_{1}}$y${\displaystyle g_{2}}$, escrito como${\displaystyle GED(g_{1},g_{2})}$puede definirse como

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$

dónde${\ Displaystyle {\ mathcal {P}} (g_ {1}, g_ {2})}$denota el conjunto de rutas de edición que transforman${\displaystyle g_{1}}$en (un grafo isomorfo a)${\displaystyle g_{2}}$y${\displaystyle c(e)\geq 0}$es el costo de cada operación de edición de gráfico${\displaystyle e}$.

El conjunto de operadores elementales de edición de grafos normalmente incluye:

Inserción de vértices para introducir un único vértice nuevo y etiquetado en un grafo.

Eliminación de vértices para eliminar un único vértice (a menudo desconectado) de un grafo.

Sustitución de vértices para cambiar la etiqueta (o el color) de un vértice determinado.

Inserción de aristas para introducir una nueva arista de color entre un par de vértices.

Eliminación de aristas para eliminar una sola arista entre un par de vértices.

Sustitución de bordes para cambiar la etiqueta (o el color) de un borde determinado.

Otros operadores, aunque menos comunes, incluyen operaciones como la división de aristas , que introduce un nuevo vértice en una arista (creando también una nueva arista), y la contracción de aristas , que elimina vértices de grado dos entre aristas (del mismo color). Si bien estos operadores de edición complejos pueden definirse en términos de transformaciones más elementales, su uso permite una parametrización más precisa de la función de coste.${\displaystyle c}$cuando el operador es más barato que la suma de sus componentes.

En ^{[ 11 ] [ 12 ] [ 13 ] se presenta un análisis profundo de los operadores de edición de grafos elementales.}

Y se han presentado algunos métodos para deducir automáticamente estos operadores elementales de edición de grafos. ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ]} Y algunos algoritmos aprenden estos costos en línea: ^{[ 19 ]}

La distancia de edición de grafos encuentra aplicaciones en el reconocimiento de escritura a mano , ^{[ 20 ]} el reconocimiento de huellas dactilares ^{[ 21 ]} y la quimioinformática . ^{[ 22 ]}

Los algoritmos exactos para calcular la distancia de edición entre dos grafos suelen transformar el problema en uno de encontrar la ruta de edición de coste mínimo entre ambos. El cálculo de la ruta de edición óptima se plantea como una búsqueda de rutas o un problema de ruta más corta , que a menudo se implementa mediante un algoritmo de búsqueda A* .

Además de los algoritmos exactos, también se conocen varios algoritmos de aproximación eficientes. La mayoría de ellos tienen un tiempo de cálculo cúbico ^{[ 23 ] [ 24 ] [ 25 ] [ 26 ].}

^{[ 27 ]} Sin embargo, el tiempo de ejecución de al menos un algoritmo es lineal en el número de nodos, aunque sigue siendo cúbico en el grado del nodo. ^{[ 28 ]}

A pesar de que los algoritmos anteriores a veces funcionan bien en la práctica, en general el problema de calcular la distancia de edición de grafos es NP-difícil (para una demostración disponible en línea, consulte la Sección 2 de Zeng et al. ), e incluso es difícil de aproximar (formalmente, es APX -difícil ^{[ 29 ]} ).

La distancia de edición de árbol (TED) representa el costo mínimo de transformar un árbol en otro utilizando tres operaciones: inserción, eliminación y reemplazo. El primer algoritmo TED de tiempo polinomial fue propuesto por Tai en 1979. ^{[ 30 ]} En 1989, Kaizhong Zhang y Dennis Shasha propusieron el algoritmo TED más conocido, ^{[ 31 ]} que introdujo técnicas de programación dinámica (DP) para resolver TED y tiene una complejidad temporal en el peor de los casos de O(n ⁴ ). Este método emplea una serie de tablas DP, donde cada tabla calcula la distancia de edición entre una subparte del primer árbol de entrada y una subparte del segundo árbol de entrada. Desde entonces, importantes esfuerzos de investigación ^{[ 32 ] [ 33 ] [ 34 ]} se han centrado en mejorar su complejidad temporal secuencial, y se ha demostrado que O(n ³ ) es el límite teórico más bajo. ^{[ 35 ]}

• X-TED