How to compute a node similarity matrix for two graphs?
1
1
Entering edit mode
6.5 years ago

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 • 4.6k views
ADD COMMENT
2
Entering edit mode
6.5 years ago
raunakms ★ 1.1k

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")
ADD COMMENT
0
Entering edit mode

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 upto X1000

ADD REPLY
0
Entering edit mode

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"

ADD REPLY
1
Entering edit mode

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!

ADD REPLY
0
Entering edit mode

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

ADD REPLY
0
Entering edit mode

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. 

ADD REPLY
0
Entering edit mode

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")
ADD REPLY
0
Entering edit mode

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

I don't know the reason of error

ADD REPLY
0
Entering edit mode

thank you for your complete answer

ADD REPLY

Login before adding your answer.

Traffic: 2175 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6