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

Hello there, i need to solve this problem: I have 2 different bi-partite weighted graph, g1 and g2 and i would like to measure their similarity, g1 and g2 may have different number of vertex and edges and they are a result of a clustering algorithm over different data-sets.

Ideas,hints,thoughts are HIGHLY appreciated. Best, Francesco.

share|improve this question
    
It would help if you could specify some additional criterion for your measure. otherwise you could just check for graph isomorphism. –  Jernej Dec 20 '12 at 9:27
    
The similarity measure should have values between 0 and 1. I image it could be calculated like 1 - some_distance_measure d(g1,g2) where d(g1 , g2) = 0 if g1 = g2, d(g1,g2) = d(g2,g1). I hope I made myself clear. –  Francesco Dec 20 '12 at 11:34
    
And what exactly should this measure resemble? In what way do you define graph similarity? –  Jernej Dec 20 '12 at 12:29
    
The question is not defined enough. What makes two bipartite graphs similar in your application? There are tons of possibilities. –  Brendan McKay Dec 20 '12 at 13:05
    
I would consider similar bipartite graph which share same vertex and edges with same weights. Thank you all –  Francesco Dec 20 '12 at 14:12
show 3 more comments

2 Answers

up vote 1 down vote accepted

Is it enough to have something which is defined or do you also want it to be relatively easy to compute?

We can say (as you do) that distance is $0$ when and only when the two graphs are identical in the sense that they have equal numbers of vertices and edges and corresponding edges have the same weight. But it can be a very hard problem to (always) decide if the distance is actually $0.$ It is actually hardest when the weights are all $0,1.$ If the graphs are small you can try every possible way of matching them up. You can be more clever about it than that but it is not easy for large graphs.

Suppose first that there is a given labeling of the vertices $x_1,x_2,\cdots ,x_m;y_1,y_2,\cdots,y_n$ with one part given then the other. Then can represent the graph by the $m \times n$ matrix $A$ whose $i,j$ entry $a_{ij}$ is the ( non-negative) weight of the edge $(x_i,y_j).$ For convenience let $a_{ij}=0$ when $i \gt m$ and/or $j \gt n.$

Then the distance between two labelled bipartite graphs with matrices $A$ and $B$ could be defined as $\sqrt{\sum(a_{ij}-b_{ij})^2}$ or perhaps $\sqrt{\frac{\sum(a_{ij}-b_{ij})^2}{\sum(a_{ij}+b_{ij})^2}}$ if we want maximum distance $1$ (here, exactly when an edge with positive weight in one graph has weight $0$ in the other.)

Now for unlabeled weighted bipartite graphs we could define the distance as the minimum of the distance over all possible orderings. That is a clean clear definition but entirely unpractical in the context of all finite weighted bipartite graphs.

Perhaps in a given setting there is more structure such as trees where each has an obvious dominant heavy spine which is a path with lighter $2$ and $3$ vertex paths hanging off it. Then we (perhaps) just have to try two orders for the path and consider insertions and deletions.

share|improve this answer
    
Yes, i thought that the euclidean distance between matrices could be a solution. By the way in both matrix A and B we should have the union of the vertex contained in both matrices. Fortunately my graphs are all labeled. –  Francesco Dec 21 '12 at 9:42
    
So you know ahead of time which edge on g2 should be compared to a given edge in g1? That would make the answer much easier. –  Aaron Meyerowitz Dec 21 '12 at 17:52
    
Just another thing, i've used the measure you gave me and worked nicely,by the way can you give me some reference to this measure? –  Francesco Feb 4 '13 at 15:17
    
I'm glad. It was just an easy thing to suggest for a hard problem. –  Aaron Meyerowitz Feb 4 '13 at 22:49
add comment

You might try tackling the problem from the other end in more detail: given a (large) set S of relational structures, what functions from SxS to the real interval [0,1] will serve as similarity measures?

If you can place a partial order on S and ask that the measure preserve some aspects of that order, that will limit the class of functions quite a bit. If there is a natural topology on S, you may want f to be invariant under certain induced homeomorphisms of S x S . If you want to conclude some algebraic relations from two nearly similar structures, you might try modding out S by those algebraic relations (or understand why you can't) and see how f should vary (or not vary) across each equivalence class.

These are detailed ways of asking "what do you want to measure really?" and "what are you going to do with (ask of) the measure when you get it?" .

Gerhard "Ask Me About System Design" Paseman, 2012.12.20

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.