R igraph：最短路径提取

Question

这是我第一次使用图形和 R igraph 包，我需要一些处理图形对象的帮助。

我想达到的目标：
从给定的接触矩阵中提取节点之间的最短置信路径。自信是指边缘权重高于相邻边缘。

示例：

一个

m <- read.table(row.names = 1, header = TRUE, text = 
    "  A   B   C   D   E   F
     A 0   1   1   1   1   5
     B 1   0   1   1e2 1e2 1
     C 1   1   0   1   1   1
     D 1   1e2 1   0   1e2 1
     E 1   1e2 1   1e2 0   1
     F 5   1   1   1   1   0")
m <- as.matrix(m)
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")

在矩阵 m 中，B-D-E 之间有一个集群（集团？）（即，这些节点之间的边际权重很高）。但是，由于 A 和 F 之间存在权重，即使边缘权重很低（只有 5），我也在那里得到集群。
问题A：如何只提取那些边缘权重高的簇？我可以使用 m[which(m <= 5)] <- 0 将这些联系人转换为 0，但我希望 igraph 包中有更多的 "mathy" 解决方案。

B

m <- read.table(row.names = 1, header = TRUE, text = 
    "  A   B   C   D   E   F
     A 0   1   1   5   1   1
     B 1   0   1   1e2 1e2 1
     C 1   1   0   1   1   1
     D 5   1e2 1   0   1e2 1
     E 1   1e2 1   1e2 0   1
     F 1   1   1   1   1   0")
m <- as.matrix(m)
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE)
sp <- shortest.paths(ig, algorithm = "dijkstra")

在矩阵 m 中，B-D-E 之间存在簇，但由于 A 和 B 之间的权重较低 - A 也连接到这个集群。
问题B：如果边权重低，如何不将节点分配给集群？

这是我的第一个问题，如果您需要说明或更好的示例，我会改进我的问题。

Answer 1

首先，很高兴知道在查找路径时，igraph 将权重理解为 成本， 即在权重较高的边上，行进成本较高，因此它会考虑缩短总权重较低的路径。把它变成相反的很容易，只要取你的权重的倒数（1 / E(ig)$weight）。两个顶点之间可能只有一条最短路径，但有时会有更多条同样短的路径。您可以查找所有这些 (all_shortest_paths)，或者告诉 igraph return 每对顶点 (shortest_paths) 只有最短的一个。这些方法的每次调用 returns 是从一个选定顶点开始的路径，要获得所有对之间的路径，您需要为每个顶点调用一次（好的，在无向图中，调用一半就足够了的顶点）。制定我到目前为止解释的内容：

spaths <- lapply(V(ig),
                 function(v){
                     all_shortest_paths(ig, v,
                                        weight = 1 / E(ig)$weight
                     )
                 }
           )

这里spaths将是一个列表列表，访问从C到所有顶点的路径是这样的：

spaths$C$res

[[1]]
+ 2/6 vertices, named:
[1] C A
[[2]]
+ 2/6 vertices, named:
[1] C B
[[3]]
+ 1/6 vertex, named:
[1] C
[[4]]
+ 2/6 vertices, named:
[1] C D
[[5]]
+ 2/6 vertices, named:
[1] C E
[[6]]
+ 2/6 vertices, named:
[1] C F

spaths$C$res[[2]] # this is the path from `C` to `B`,
                  # a vector of 2 vertices

注意，第三个元素实际上是从C到它自己，你可以忽略它，或者提供一个所有其他顶点的向量给all_shortest_paths的to参数。此外，在您的示例中，所有最短路径的长度均为 1，但是如果我将 B--E 的权重设置为 1 而不是 100，我们会看到该方法有效，并且从 B 到 E 最短路径将是 B-D-E.

关于你的第二个问题，这里不是很清楚你想实现什么，特别是你如何获得这些集群？如果你想找到社区，即连接更紧密的顶点组，同时考虑边权重，有很多方法可以做到这一点，所有那些在 igraph 中名为 cluster_[...] 或 community.[...] 的方法。例如，如果我们运行你图上的 fastgreedy 方法，它将检测你提到的集群：

fg <- fastgreedy.community(ig, weights = E(ig)$weight)

IGRAPH clustering fast greedy, groups: 2, mod: 0.059
+ groups:
$`1`
[1] "A" "C" "F"
$`2`
[1] "B" "D" "E"

所以这里我们有 B, D, E 集群，它与更高权重的边相连。如果我们运行没有权重的相同方法，所有顶点将属于一个组 (fastgreedy.community(ig, weights = NULL))。请注意，在社区检测中，igraph 将权重理解为 强度， 因此与较高权重边连接的顶点更有可能聚集在一起，这与它在计算路径时的工作方式有点相反。

R igraph：最短路径提取

R igraph: shortest path extraction

r

dijkstra

shortest-path

igraph