将边列表转换为路径长度列表

Question

我正在 R 中使用加权无向网络。我有一个直接连接的边和它们之间的权重的列表。权重表示顶点之间的距离。我想要一个所有顶点之间的路径距离的列表。我的数据如下所示：

library(dplyr)
library(igraph)

set.seed(123)

edgelist <- data.frame(
  node1 = sample(1:10, 30, replace = T),
  node2 = sample(1:10, 30, replace = T),
  weight = runif(30, min = 0, max = 5)
)

igraph::distances()

将创建一个路径长度矩阵。

g <- graph_from_data_frame(edgelist, directed = F)

dm <- distances(g, weight = E(g)$weight)

但是，这对我来说并不理想，因为我有 29000 个节点，而一个包含 8 亿个单元的矩阵太重而无法使用。我可以忽略对角线，因为节点不是自连接的，并且由于网络是无向的，我只需要矩阵的上（或下）三角形。因此，为了减少计算时间，我想要一个 data.frame 或具有 3 列的类似对象类型：“verticeA”、“verticeB”、“verticeA 和 verticeB 之间的路径长度”。

给定初始边缘列表，如何实现这一目标？计算效率是这里的关键，因为我需要使用很多大型边缘列表来完成此操作。

以下是我尝试过的一些事情：

pl <- as.table(dm) %>% 
  data.frame() %>%
  mutate_all(as.numeric) %>%
  filter(Var1 != Var2) %>%
  mutate(
    verticeA = pmin(Var1, Var2),
    verticeB = pmax(Var1, Var2)
  ) %>%
  select(-Var1, -Var2) %>%
  distinct(verticeA, verticeB, .keep_all = T) %>%
  rename(distance = Freq)

计算这个会让R冻结，可能是因为我的数据太大了。

ut <- dm[upper.tri((dm))]

检索上三角形，我想它可以与

colnames(dm)

和

rownames(dm)

结合使用，但我不太清楚如何使用。

Answer 1

使用问题中的数据示例，您可以生成按

distances

顶点分组的

from

，而不是生成完整距离表。

g <- graph_from_data_frame(edgelist, directed = F) %>%
  simplify(edge.attr.comb = "min")

df <- as.data.frame(
  t(combn(names(V(g)), 2))
) %>%
  setNames(c("from", "to")) %>%
  mutate(dist = t(distances(g, first(from), to)), .by = from)

你将获得

   from to      dist
1     3 10 0.9384556
2     3  2 2.5375587
3     3  6 2.7464233
4     3  5 1.4064305
5     3  4 5.1460144
6     3  9 3.4818967
7     3  8 3.3529676
8     3  7 3.9114715
9     3  1 4.5721909
10   10  2 1.5991031
11   10  6 3.0255022
12   10  5 0.4679749
13   10  4 4.3620589
14   10  9 2.6979412
15   10  8 2.4145120
16   10  7 3.9329983
17   10  1 5.4715983
18    2  6 1.8343116
19    2  5 2.0670780
20    2  4 2.7629559
21    2  9 1.0988382
22    2  8 1.8103096
23    2  7 2.3338952
24    2  1 3.8724953
25    6  5 2.5575273
26    6  4 2.3995912
27    6  9 0.7354735
28    6  8 1.4469449
29    6  7 4.1682068
30    6  1 5.7068069
31    5  4 4.8300339
32    5  9 3.1659162
33    5  8 2.8824869
34    5  7 4.4009732
35    5  1 5.9395733
36    4  9 1.6641177
37    4  8 2.3755892
38    4  7 4.7386347
39    4  1 6.2772348
40    9  8 0.7114715
41    9  7 3.4327334
42    9  1 4.9713334
43    8  7 4.1442048
44    8  1 5.6828049
45    7  1 1.5386001