igraph：最短路径提取

Question

igraph：最短路径提取

3

这是我第一次使用图形和 R igraph 包进行工作，需要处理图形对象并寻求帮助。

我想要实现的目标：从给定的联系矩阵中提取节点之间最短的可信路径。这里的可信是指边的权重高于相邻边的情况。

举例说明： A

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软件包中有更多“数学”解决方案。

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：如果边缘权重很低，如何不将节点分配给聚类？

这是我的第一个问题，如果需要澄清或更好的例子，我会改进我的问题。

- user54101

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- deeenes · Accepted Answer

首先，需要知道当查找路径时，igraph将权重视为“成本”，即在权重较高的边上行进需要花费更多，因此它会将总权重较低的路径视为更短的路径。如果要将其转换为相反的情况，只需取权重的倒数（1 / E(ig)$weight）。在两个顶点之间可能只有一条最短路径，但有时还会有多条同样短的路径。您可以查找所有这些路径（all_shortest_paths），或告诉igraph仅返回每对顶点中最短的一个（shortest_paths）。每次调用这些方法都会返回从一个选定的顶点到达的路径，要获得所有对之间的路径，则需要为每个顶点调用一次（好吧，在无向图中，仅需要对一半的顶点进行调用）。总结以上内容：

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 将权重视为“强度”，因此连接更高权重边的顶点更有可能聚集在一起，这与计算路径的方式有点相反。