# Comparing two graphs

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.

• 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 – vzn Mar 13 '14 at 18:21 