R-找到鄰居的鄰居并將它們存盤在唯一的鄰接矩陣中

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包含表示節點4和的列的值 1 8，但不表示節點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

這篇文章提出了一個類似的問題，但使用了不同的語言并且涉及到稍微不同的解決方案。

注意：理想的解決方案將擴展到具有 100 個節點的網路并運行數萬次，所以我希望有一個高效的解決方案。

uj5u.com熱心網友回復：

您可以嘗試使用下面的代碼 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

uj5u.com熱心網友回復：

這是距離表的簡單總結。

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 步外等，但是距離表將給出最短路徑長度，因此如果您查看長度 > 1 并且您的圖表有回圈，這只會查看最短路徑。

uj5u.com熱心網友回復：

您可以簡單地平方鄰接矩陣。(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

標籤：

上一篇：查找位數按降序排列的所有數字

下一篇：陣列演算法性能kata