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.
Best 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.