Approximate isomorphism

Usage
1

Can igraph identify approximate isomorphic graphs? also called inexact graph matching.

Thanks in advance.

2

The Mathematica interface (you tagged this question as Mathematica) cannot yet do this.

The R interface has the match_vertices functions. It is at the moment only available in R.

3

Thanks for your response. I meant to tag R but somehow ended up in M interface. Sorry for the mistake.

A follow up question: the match_vertices function can only work for A and B of the same size. what I am actually looking for is:

a graph similarity measure : minimum cost of edit path (sequence of node and edge edit operations) transforming graph G1 to graph isomorphic to G2.

Reference: networkx.algorithms.similarity.graph_edit_distance — NetworkX 2.2 documentation

I was wondering if igraph can do the same thing.

Thanks.

4

At the moment, there is no such functionality in igraph. I guess you are looking for better performance than what networkx offers? The problem is NP-complete, so another exact implementation is unlikely to make much larger graphs feasible.

Wikipedia says that there are some fast approximation algorithms. Personally, I do not have experience with these. I don’t know where one can find an implementation and how accurate they are.

5

Thanks so much for your quick response. I appreciate that.

I am actually trying to find such functionality in R, but networkx is only for python.

But thanks for clarifying that igraph does not offer that for now. That helps.

Hope you have nice day.

6

Should you wish to contribute this functionality to igraph, it would be very welcome! Of course, it is far from a trivial task …

Here are some tips you can try:

  • Pad the smaller graph with isolated vertices so its size matches the larger one, then use match_vertices
  • Sometimes it’s useful to characterize the “similarity” of two graphs indirectly, by computing a vector of several global graph properties for both graphs, then measuring the distance of these vectors. I would try spectral properties first.
7

Thank you for your response. I wish I were able to contribute, but my knowledge on developing a functionality is basically zero.

Also thanks for your suggestions. I will definitely try them.