Métrica para calcular la similitud estructural entre dos grafos dirigidos

Question

Estoy trabajando en un pequeño proyecto en el que trato de comparar dirigido a-cíclico de los gráficos. Decir que tengo (dirigida) tres gráficos:

1)

                    X 
                  /   \
                 /     \
START - X - X - X - X - END
         \       
          \   
            X  

2)

         X - X - X - X
       /              \
      /                \
START -  X - X - X - X - END
      \                /
       \              /
         X - X - X - X 

3)

                    X - X           X - X - X 
                  /               /          \
                 /               /            \
START - X - X - X - X - X - X - X - X - X - X - END

Tenga en cuenta que las etiquetas (X) no son de importancia; sólo estoy interesado en las propiedades estructurales y similitudes entre las gráficas. Tienes alguna sugerencia para la literatura o cualquier ingeniosas ideas de cómo calcular la estructura de distancia o similitud entre los gráficos de este tipo?

Muchas gracias!

Answer 1

Creo que usted está buscando un gráfico del núcleo.

Una rápida búsqueda en la web me dio un par de papeles para empezar:

• Gráfico De Granos. S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, Karsten M. Borgwardt; 11(Apr):1201-1242, 2010
• Sato et al. Gráfico acíclico dirigido núcleos estructurales de análisis de ARN. BMC Bioinformatics 2008, 9:318 doi:10.1186/1471-2105-9-318