# Similarity measure between 2 bi-partite graph.

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.

-
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

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.

-
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