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

I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). Graphs are calculated for each frame. The structure of the graph changes when the objects are moved or modified in the video.

I have two graphs whose number of vertices and the edges between them keep changing with time. I want a similarity metric between two such graphs.

The method used currently is to encode the changes in graph structure in a string. So, we get two strings representing the change in graph structure with time. Now substring matching is done between the two strings and this is used to determine the similarity of the two videos.

I am not sure this is the right way to compare the similarity of two graphs. Something more mathematically concrete should exist. What are some techniques which might be helpful to me? I am not entirely sure whether this is the right place to post this but any pointers to what I should read to model this would be helpful.

share|improve this question
    
I think the term you want to Google on is "graph edit distance". A relatively recent survey (2010) from GAO et al bit.ly/15pOkWp But, what you are doing seems kosher. They actually suggest just what you're doing on page 118 in the paragraph beginning "A graph may be an attributed relational..." –  Kelly Davis Aug 30 '13 at 14:10
    
Thanks for the tip and the link to the paper. –  web_ninja Aug 30 '13 at 14:49

1 Answer 1

If you have two graphs, there is no point to measure their similarity using strings. Actually there are lot of researches going on measuring graph similarity.

I also doing research on it and I implemented a algorithm that use neighbor matching to measure the similarity of two directed graphs. I refer existing research paper and implemented in Java.

You can find more details about that in MEASURING GRAPH SIMILARITY USING NEIGHBOR MATCHING. Actually that algorithm should also optimize to improve the accuracy. You can try this algorithm if you are interested and you will have to change it according to you requirement.

share|improve this answer

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.