How to compute a node similarity matrix for two graphs?

Question

[ishanee.india]

I wish to do graph alignment using the R package GraphAlignment. As an input, it wants the node similarity matrix. I have 4 adjacency matrices, with same vertices (1000 in number) and will have to compute node similarity matrix for each possible pair. I tried my luck with a lot of search, and ended up with some mathematical functions and algorithms to compute it. So, is there any easy way to compute it, or should I use R to compute a matrix using one of the mathematical functions defined to construct a similarity matrix?

Am in a fix, and started to learn R recently. Any help would be appreciated!

Answer 1

[raunakms]

You can easily solve the problem using the igraph R package. The function graph.intersection is very handy for graph comparison purposes.

library("igraph")

### Suppose adj_1, adj_2, adj_3, adj_4 are your four adjacency matrices
### convert the adjacency matrices into an igraph object using graph.adjacency function
g_1 <- graph.adjacency(adj_1, mode="undirected", weighted=NULL, diag=TRUE)
g_2 <- graph.adjacency(adj_2, mode="undirected", weighted=NULL, diag=TRUE)
g_3 <- graph.adjacency(adj_3, mode="undirected", weighted=NULL, diag=TRUE)
g_4 <- graph.adjacency(adj_4, mode="undirected", weighted=NULL, diag=TRUE)

### Compute graph similarity (intersection of vertices and edges between the graphs)
g_sim <- graph.intersection(g_1, g_2, g_3, g_4, byname = "auto", keep.all.vertices = FALSE)

### Compute adjacency matrix of the g_sim graph
adj_sim <- get.adjacency(g_sim, type="both")

[ishanee.india]

Well, upon doing, am getting something like this:

1000 x 1000 sparse Matrix of class "dgCMatrix"
X1  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X2  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X3  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X4  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X5  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X6  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X7  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X8  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X9  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......
X12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......

for all up to X1000

[raunakms]

Yes adj_sim gives you a "dot" represents no edge between the vertices and "1" represents an edge exist between the vertices.

adj_sim <- as.matrix(get.adjacency(g_sim, type="both"))

gives you a binary matrix with "1" or "0"

[ishanee.india]

Ok!

Well, I am getting all as zero. Is that okay to get a result like this? This implies there is no similarity between two graphs if I align them, they are completely different!

[raunakms]

yes the script is correct. I've extensively applied it for my projects.

[areyoujokingme]

What if we don't want a binary ruling on similarity? What if we want a number between 0 and 1, as in the Jaccard index? Igraph's similarity.jaccard(ig, ig2, vids=c(V(ig)$name[1], V(ig2)$name[1])) gives back a matrix that is 2x2 (#vids by #vids). How does one interpret this matrix? The diagonals are 1 in my case and the off diagonals are 0.

[raunakms]

If you have a directed graph and if you choose different "mode" options, it calculates the indices accordingly. Try varying mode options and see the changes in the resulting values.

dat <- matrix(c(0, 0, 0, 0, 0, 0, 0, 0, 
                 0, 0, 1, 0, 1, 0, 0, 0, 
                 0, 0, 0, 0, 1, 0, 0, 0, 
                 0, 0, 1, 0, 0, 0, 0, 1, 
                 1, 1, 1, 0, 0, 0, 0, 0, 
                 0, 1, 1, 0, 0, 0, 0, 0,
                 0, 0, 1, 1, 0, 1, 0, 0, 
                 0, 0, 1, 1, 1, 0, 0, 0), 
               nrow=8, ncol=8, byrow=TRUE)

library("igraph")
g <- graph.adjacency(dat, mode="directed", weighted=NULL) 
similarity(g, method = "jaccard", mode="in")

[zizigolu]

Sorry dear raunakms may you please consider my post taking intersection between two networks

I don't know the reason of error

[zizigolu]

Thank you for your complete answer