Medir la "similitud" de los gráficos

Question

Estoy buscando alguna medida numérica $s$ que puede decirme lo "similares" que son dos gráficos, y es relativamente fácil calcular/estimar su valor.

Sé que no es una pregunta muy precisa, así que aquí hay algo más de información. Por ejemplo, algo como esto es útil:

• si los gráficos son isomorfos, entonces $s=0$ .
• si los gráficos no son isomorfos, entonces $s>0$ .
• si sólo se cambian unas pocas aristas (se añaden/eliminan) en un gráfico, el valor de la similitud entre el gráfico antiguo y el nuevo es pequeño
• si los gráficos difieren más, entonces $s$ es grande

Hay varias medidas con propiedades similares. Me pregunto si hay alguna los más utilizados que son fáciles de estimar en un ordenador.

Se agradecen los enlaces, las sugerencias o simplemente las palabras clave para buscar. Estoy especialmente interesado en cualquier resultado anterior sobre esto.

EDITAR También me resulta útil tener algo que sólo funcione entre gráficos de igual número de vértices. Una posibilidad sería utilizar algún tipo de distancia de edición. Pero estimar esta distancia de edición no es un problema sencillo en absoluto debido a la dificultad de elegir un etiquetado de vértices "coincidente" entre los dos gráficos.

Answer 1

Cuando escribes: "Hay varias medidas con propiedades similares", parece que ya conoces más de una respuesta posible a tu pregunta, pero no das ningún ejemplo, así que no hay forma de saber si ya conoces algo que podríamos sugerir. De todos modos, aquí tienes una posibilidad, para grafos con el mismo número (finito) de vértices:

A cada gráfico en $n$ vértices, asignar un vector $\bf v$ en ${\bf R}^n$ dado por el secuencia de grados del gráfico, es decir, una lista de los grados de los vértices, ordenados de mayor a menor. Entonces, dados dos grafos, sea $s$ sea la distancia euclidiana ordinaria entre los vectores correspondientes a los dos grafos.

Buenas noticias: esto satisface al menos dos de tus cuatro puntos, y debería ser muy fácil de calcular.

Malas noticias: puede ser cero incluso para los grafos que no son isomorfos (pero por supuesto sabes que eso es inevitable, con los conocimientos actuales).

No es una noticia de aquí ni de allá: no tengo ni idea de si esto es "de uso común".