1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\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 '14 at 18:21
2
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\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 '14 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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