This is a test version of Biostars. For the public version, visit https://www.biostars.org.
How to compute a node similarity matrix for two graphs?

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!

r igraph graphalignment
• 8,177 views • link
updated by Ram Ram • written by ishanee.india • ishanee.india

1 answer

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")
• 0 views • link
written by raunakms raunakms

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

• 0 views • link
updated by Ram Ram • written by ishanee.india • ishanee.india

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"

• 0 views • link
updated by Ram Ram • written by raunakms raunakms

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!

• 0 views • link
updated by Ram Ram • written by ishanee.india • ishanee.india

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

• 0 views • link
written by raunakms raunakms

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.

• 0 views • link
updated by Ram Ram • written by areyoujokingme • areyoujokingme

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")
• 0 views • link
updated by Ram Ram • written by raunakms raunakms

Thank you for your complete answer

• 1 views • link
updated by Ram Ram • written by zizigolu zizigolu

Log in to answer this question.

More posts like this