R - finding the neighbors of neighbors and storing them in a unique adjacency matrix
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:
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.
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
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.
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