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


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


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


                    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!

  • $\begingroup$ 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". $\endgroup$ – ttnphns Aug 31 '14 at 10:36
  • $\begingroup$ 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? $\endgroup$ – Folgert Karsdorp Aug 31 '14 at 10:50

I think you are looking for a graph kernel.

A quick web search gave me a couple of papers to start:

  • Graph Kernels. S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, Karsten M. Borgwardt; 11(Apr):1201−1242, 2010
  • Sato et al. Directed acyclic graph kernels for structural RNA analysis. BMC Bioinformatics 2008, 9:318 doi:10.1186/1471-2105-9-318
  • $\begingroup$ Thanks! That definitely seems like something to look into. $\endgroup$ – Folgert Karsdorp Sep 1 '14 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.