I have a quite big graph which has millions of nodes and edges. I modify the graph using an algorithm which only changes small portion of edges. At then end, I'd like to investigate how the algorithm affects the graph. There are a couple of options I have considered, but neither are appropriate.

1) compare the graph metrics (e.g. avg nodes degree, avg. coefficient clustering) for two graphs. The problem is as the algorithm only affects small portion of edges, and as there are great number of nodes and edges, the reported values are almost the same.

2) sample portion of each graph and find graph metrics on the sampled graphs. Again, the reported numbers are quire similar.

Is there any metric or technique to compare only subgraphs of two graphs? That is, I would like to consider only the modified nodes in the comparison.

  • $\begingroup$ could you describe what kind of algorithm is being applied? what do you want to determine about the differences? yes graph "diff" algorithms seem not to have been explored much, there is some theory that might be applicable.... see also techniques for analyzing series of graphs tcs.se (no answer there yet). a simple technique is to determine which nodes changed and then build old/new subgraphs out of them and look at how they interrelate etc $\endgroup$
    – vzn
    Mar 13, 2014 at 18:21

1 Answer 1


here is one table about the different similarity measures which can be found in this paper https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf

enter image description here

  • $\begingroup$ If you want to apply them to the big graph, you need to know the characteristics of the big graph to make it more proper. For example, the sparsity is one of the most important features. $\endgroup$
    – user17918
    Mar 13, 2014 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.