2

I have two graphs (g1) and (g2), the number of nodes and degree are different in both graphics. I would like to calculate "in some way" how similar are both graphs. I thought in using something like a Jaccard index, the approach would be something like this:

g1 <- erdos.renyi.game(100, 0.3)
g2 <- erdos.renyi.game(100, 0.3) 
g.union <- graph.union(g1, g2)
g.intersect <- graph.intersection(g1, g2, keep.all.vertices=F)

sim.index <- ecount(g.intersect)/ecount(g.union)

But I don't know if this make any sense,

Thanks in advance

user2380782
  • 1,542
  • 4
  • 22
  • 60
  • `graph.union` and `graph.intersection` use the vertex labels, so if you relabeled the vertices (but didn't change the structure of the graphs) you would get a different answer. If you want a similarity measure that relies on structure instead of vertex labels, you might try the graph edit distance, which has been discussed [here](http://stackoverflow.com/questions/16399597/edit-distance-between-two-graphs). Unfortunately computing it is NP-hard, and it doesn't look like there's an implementation in igraph. – josliber Mar 30 '15 at 17:45
  • Chapter 6 of Practical Graph Mining with R (Samatova, et al) explains Neuman Kernels and how to calculate the "relatedness" of two network graphs. The example on 153-156 uses the packages igraph and ProximityMeasure. – lawyeR Mar 30 '15 at 18:00
  • Thanks @lawyeR, what I cannot find is the package ProximityMeasure, I think the library GraphClusterAnalysis can do something similar but I cannot find it as well – user2380782 Mar 30 '15 at 18:42
  • Here is the Chapter I was referring to -- http://www.csc.ncsu.edu/faculty/samatova/practical-graph-mining-with-R/sample/chapter_6_Proximity.pdf – lawyeR Mar 30 '15 at 19:35
  • did you check this? https://rdrr.io/bioc/BiRewire/man/birewire.similarity.html – jjrr Mar 22 '19 at 14:28

0 Answers0