R - finding the neighbors of neighbors and storing them in a unique adjacency matrix

user_3724318 0
Viewed 211

A is an adjacency matrix stored as a matrix object:

                   #1 2 3 4 5 6 7 8 9
A <- matrix(data=c( 0,0,1,1,0,0,0,1,0,  #1
                    0,0,0,0,1,0,0,0,0,  #2
                    1,0,0,0,0,0,0,0,0,  #3
                    1,0,0,0,0,0,0,0,1,  #4
                    0,1,0,0,0,1,0,0,0,  #5
                    0,0,0,0,1,0,0,0,0,  #6
                    0,0,0,0,0,0,0,0,0,  #7
                    1,0,0,0,0,0,0,0,0,  #8
                    0,0,0,1,0,0,0,0,0 ),#9
                    nrow=9, ncol=9)

The graph of A looks like this:

enter image description here

I am trying to identify the neighbors of neighbors, and to create a new adjacency matrix N with values that capture the neighbors of some node j who are exactly one step away from a given node i.

In A for example, 3 is neighbors with 1, and 1 is neighbors with 4 and 8. But 3 is neighbors with neither 4 nor 8. In the desired adjacency matrix N, I want the row/column representing 3 to contain a value of 1 for columns that represent nodes 4 and 8, but not node 1. The solution matrix N should look like this:

                   #1 2 3 4 5 6 7 8 9
N <- matrix(data=c( 0,0,0,0,0,0,0,0,1,  #1
                    0,0,0,0,0,1,0,0,0,  #2
                    0,0,0,1,0,0,0,1,0,  #3
                    0,0,1,0,0,0,0,1,0,  #4
                    0,0,0,0,0,0,0,0,0,  #5
                    0,1,0,0,0,0,0,0,0,  #6
                    0,0,0,0,0,0,0,0,0,  #7
                    0,0,1,1,0,0,0,0,0,  #8
                    1,0,0,0,0,0,0,0,0 ),#9
            nrow=9, ncol=9)

For clarity, here are the neighbors of neighbors in A that become the information stored in N.

#1: 9
#2: 6
#3: 4, 8
#4: 8, 3
#5: -
#6: 2
#7: -
#8: 3, 4
#9: 1

This post asks a similar question, but uses a different language and involves a slightly different solution.

Note: the ideal solution would scale to networks with 100 nodes and run tens of thousands of times, so I'm hoping for a solution that's efficient.

igraph graph r matrix algorithm
3 Answers

You can try the code below using ego

g <- graph_from_adjacency_matrix(A, "undirected")
v <- rep(0, vcount(g))
N <- sapply(ego(g, order = 2, mindist = 2), function(k) replace(v, k, 1))

and you will obtain

> N
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    0    0    0    0    0    0    0    0    1
 [2,]    0    0    0    0    0    1    0    0    0
 [3,]    0    0    0    1    0    0    0    1    0
 [4,]    0    0    1    0    0    0    0    1    0
 [5,]    0    0    0    0    0    0    0    0    0
 [6,]    0    1    0    0    0    0    0    0    0
 [7,]    0    0    0    0    0    0    0    0    0
 [8,]    0    0    1    1    0    0    0    0    0
 [9,]    1    0    0    0    0    0    0    0    0

or a more compact result

> ego(g, order = 2, mindist = 2)
[[1]]
+ 1/9 vertex, from da0d22c:
[1] 9

[[2]]
+ 1/9 vertex, from da0d22c:
[1] 6

[[3]]
+ 2/9 vertices, from da0d22c:
[1] 4 8

[[4]]
+ 2/9 vertices, from da0d22c:
[1] 3 8

[[5]]
+ 0/9 vertices, from da0d22c:

[[6]]
+ 1/9 vertex, from da0d22c:
[1] 2

[[7]]
+ 0/9 vertices, from da0d22c:

[[8]]
+ 2/9 vertices, from da0d22c:
[1] 3 4

[[9]]
+ 1/9 vertex, from da0d22c:
[1] 1
user_121587570

This is a simple summary of the distances table.

library(igraph)
g = graph_from_adjacency_matrix(A, mode = "undirected")
dists = distances(g)

(result = ifelse(dists == 2, 1, 0))
 #     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 # [1,]    0    0    0    0    0    0    0    0    1
 # [2,]    0    0    0    0    0    1    0    0    0
 # [3,]    0    0    0    1    0    0    0    1    0
 # [4,]    0    0    1    0    0    0    0    1    0
 # [5,]    0    0    0    0    0    0    0    0    0
 # [6,]    0    1    0    0    0    0    0    0    0
 # [7,]    0    0    0    0    0    0    0    0    0
 # [8,]    0    0    1    1    0    0    0    0    0
 # [9,]    1    0    0    0    0    0    0    0    0

And this easily extends to 2 steps away, 3 steps away, etc, however the distances table will give shortest-path length, so if you look at lengths > 1 and your graph has cycles, this will only look at the shortest path.

user_9030610

You can simply square the adjacency matrix. (A^2)_ij gives the number of walks of length 2 between vertices i and j.

Note that walks can turn around and go back through the same edge where they came from. Thus the diagonal of A^2 contains the degrees: move along an edge and go back.

B <- A %*% A
diag(B) <- 0 # zero the diagonal
B <- 1*(B>0) # replace non-zero elements with 1s
user_6951320
Related