R - 找到邻居的邻居并将它们存储在唯一的邻接矩阵中

Question

A是存储为矩阵对象的邻接矩阵：

                   #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)

A 的图形如下所示：

我正在尝试识别邻居的邻居，并创建一个新的邻接矩阵 N，其值捕获某个节点 j 的邻居，这些邻居与给定的距离恰好一步节点 i.

以A为例，3与1为邻居，1与4、8为邻居。但是 3 既不是 4 也不是 8 的邻居。在所需的邻接矩阵 N 中，我希望代表 3 的 row/column 包含代表节点 4 和 8 的列的值 1，但是不是节点1。解决方案矩阵 N 应如下所示：

                   #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)

为清楚起见，这里是 A 中邻居的邻居，它们成为存储在 N 中的信息。

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

This post 问了一个类似的问题，但使用不同的语言并且涉及略有不同的解决方案。

注意：理想的解决方案将扩展到具有 100 个节点和运行数万次的网络，因此我希望有一个高效的解决方案。

Answer 1

您可以使用 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))

你将获得

> 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

或更紧凑的结果

> 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

Answer 2

这是距离的简单总结 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

这很容易扩展到 2 步远、3 步远等等，但是距离 table 将给出 最短路径 长度，因此如果您查看长度 > 1 并且您的图形有循环，这只会查看最短路径。

Answer 3

您可以简单地平方邻接矩阵。 (A^2)_ij 给出顶点 i 和 j 之间长度为 2 的步数。

请注意，行走可以掉头并从它们来自的同一条边返回。因此 A^2 的对角线包含度数：沿边移动并返回。

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

R - 找到邻居的邻居并将它们存储在唯一的邻接矩阵中

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

r

algorithm

matrix

graph

igraph