# Metric to compute structural similarity between two directed graphs

I'm working on a small project in which I try to compare directed a-cyclic graphs. Say I have (directed) three graphs:

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


Note, that the labels (X) are of no importance; I'm only interested in the structural properties and similarities between the graphs. Do you have any pointers to literature or any clever ideas how to compute the structural distance or similarity between such graphs?

Many thanks!

• It may sound - since vertex labels are of no importance - like you just want to compare images/shapes! Otherwise please elaborate on what is "structural likeness". – ttnphns Aug 31 '14 at 10:36
• In a way, I think I am interested in the shapes of the graphs. For example in my data I have graphs in which new nodes are cumulatively added. There are also graphs that start with many nodes yet only one node makes it to the end. I would consider these two types to be structural opposites. Graph theory is really not my field, so maybe you can help me with formulating my question more specific? – Folgert Karsdorp Aug 31 '14 at 10:50