MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 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

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|cite|improve this answer

Iterative method to involve neighbors' information is a subfamily of this problem. This spirit is suitable for both directed and indirected graphs, like SimRank, similarity flooding etc. I have implemented a set of algorithms (for both direct and indirected graphs) of this branch in Python. Future similarities would be appended without iteration manner. Enjoy!

Update 12/25/15: I added a C implementation of my proposed TACSim algorithm, which calculates the similarity of weighted directed graphs considering both node and edge neighbors. You can refer to my new research paper if you use it in your research.

  • Chen, Xiaming; Wang Haiyang, Qiang, Siwei; Wang, Yongkun; Jin, Yaohui; Discovering mesostructures of human mobility from city-scale data, Trans. on Big Data, 2016 (Submission).
share|cite|improve this answer

There is an increasingly-large body of work on graph kernels for determining similarity.

Here is a nice survey.

share|cite|improve this answer

Your Answer


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.