Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all,

I would like to know if there is a way to compute some measure of similarity between two ordinary graphs with weighted edges. Graphs do not share vertices and can differ in number of vertices and edges.

Any hints, suggestions and thoughts are highly appreciated.

Best, Jozef

share|improve this question
    
A weighted graph is not much different than a real (symmetric if you are not considering digraphs) matrix. A possible candidate is thus using any of the available matrix norms. –  Gjergji Zaimi Sep 10 '10 at 13:43
    
@Gjergji - what if the graphs have different numbers of vertices? –  Darsh Ranjan Sep 10 '10 at 19:36
4  
I don't think you can expect to find one good measure of similarity for graphs. Whatever measures you can come up with will depend on which application you have in mind. –  Thierry Zell Sep 11 '10 at 0:22
    
@Darsh - add empty vertices. –  Gjergji Zaimi Sep 11 '10 at 1:03
    
Treating a weighted graph as a matrix has the problem that you lose permutation invariance (or that you have to explicitly encode permutation invariance into your distance function). –  Suresh Venkat Feb 25 at 17:45
add comment

5 Answers

up vote 5 down vote accepted

If you view the weights as edge lengths then you can view each graph as a metric space, and then use the Gromov-Hausdorff distance between the two metric spaces. This may not be at all suitable for your application but it has been very useful in my own research.

share|improve this answer
1  
It might not work very well if the weights do not give you a metric space: what about the triangle inequality? –  Thierry Zell Sep 11 '10 at 0:17
1  
The weights (assuming they are non-negative) always give you a metric space. The definition of the distance between two vertices is the total weight on the lightest path between them. –  Louigi Addario-Berry Sep 11 '10 at 1:13
add comment

If all weights of edges are strictly positive, interpreting them as lengths and considering the Gromov-Hausdorff distance (see http://en.wikipedia.org/wiki/Gromov%E2%80%93Hausdorff_convergence) is perhaps a good candidate. If there are negative weights, replace them by exponentials first.

share|improve this answer
add comment

Comparing two graph structures with the same number of vertices and edges to see if they are equivalent would be the graph isomorphism problem. The graph isomorphism problem is known to be NP in complexity, but it is not known if it is NP-complete nor is it known to be solvable in polynomial time.

Comparing two graph structures with different numbers of edges and vertices would be a slightly bigger problem. Call the graph with the smaller number of vertices $G_1$ and the graph with the larger number of vertices $G_2$. Now you have to search to see if $G_1$ is isomorphic or similar to a subset of $G_2$. Depending on the relative sizes of the graphs, this could take a long time to evaluate.

If you already has a similarity metric defined for two graphs with the same number of vertices, e.g. $d(G_a,G_b)$, where $|V_a|=|V_b|$, then you could proceed as follows.

One way to attack the problem is to take the smaller graph as the template and see if you can overlay it onto the larger graph by taking a subset of the vertices of $G_2$, call it $H_n$ where $n$ can be one of the $\binom{|V_2|}{|V_1|}$ ways of picking a subgraph of $G_2$ with the same number of vertices as $G_1$. $|V_1|$= the number of vertices in $G_1$, and $|V_2|$= the number of vertices in $G_2$ in this case.

One similarity metric to use to compare two graphs with the same number of vertices would be to apply a mapping between vertices between $G_1$ and $G_2$, e.g. {$m: V_{1,a} \to V_{2,b}$}.

Then add up the number of coincident edges: for each edge in $G_1$ which connects $V_{1,i}$ and $V_{1,j}$, find the two corresponding vertices in $G_2$ , $V_{2,m(a)}$ and $V_{2,m(b)} $,and see if there is a corresponding edge is $G_2$ between these corresponding vertices.

share|improve this answer
add comment

Determine the modal vertices. Raise the power of the graphs to some power k. Normalize the modal rows. Compare these rows for sufficiently high k.

If these distributions are the same then the graphs are similar.

Following my previous post: In answer to your specific example, Connect the base version of the graph to its changing version at the vertices which are fixed. Then watch the mode Row distribution change as the graph changes using the same matrix power method I described. The mode row is the row containing the vertex, which has the most edges.

What you will get is the drift in mode frequency over time. Similarities follow.

Chris Durand

share|improve this answer
add comment

It migth be you find some useful matters in the following article:

A metric on the space of weigthed graphs, Hamed Daneshpajouh, Hamid Reza Daneshpajouh, Farzad Didehvar.

Rigth now you can find it in arxive.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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