Re: [igraph] Comparing large graphs

[Tamás Nepusz]

> If I remember right, some months ago somebody posted here about
> measures to compare networks. I looked for this post in the historial
> of the list, but I didn't find it, sorry.
This is a thread that seems related, although it is quite old:

http://lists.gnu.org/archive/html/igraph-help/2008-04/msg00009.html

However, the conclusion is still the same: there is no built-in network 
comparison measure in igraph right now. Besides the options mentioned in that 
particular thread, another possibility is to calculate the top few eigenvalues 
and eigenvectors of the adjacency matrix of the graph, and then compare these 
values and vectors. Others have studied this in much greater detail than me so 
I'd recommend to Google for "spectral graph comparison" if you are interested. 
This paper could be a good starting point:

http://www.comp.leeds.ac.uk/bmvc2008/proceedings/2005/papers/162/bmvc2005b.pdf

You can also compare the motif profiles of the graphs:

http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0015765

Yet another option that comes to my mind is to use some technique that 
compresses the graph into a much smaller matrix while preserving the most 
important structural features and then compare the matrices:

http://arxiv.org/abs/cond-mat/0703470

Best,
T.