R igraph : shortest path extraction

Question

这是我第一次使用图表和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 之间有一个簇(集团？) (即，这些节点之间的egde权重很高)。然而，由于 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:如果边权重较低，如何不将节点分配给集群？

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

Answer 1

首先，很高兴知道在查找路径时，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对于其本身，您可以忽略它，或者向 to 提供所有其他顶点的向量。 all_shortest_paths的参数。另外，在您的示例中，所有最短路径的长度均为 1，但如果我设置 B--E 的权重，例如到 1 而不是 100，我们看到该方法有效，并且从 B至E最短路径为B-D-E .

关于你的第二个问题，这里还不完全清楚你想要实现什么，特别是你如何获得这些集群？如果你想找到社区，即连接更紧密的顶点组，同时考虑到边权重，有很多方法可以实现，所有这些方法都名为 cluster_[...]或community.[...]在 igraph 中。例如，如果我们在您的图上运行 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 将权重理解为强度，因此与较高权重边连接的顶点更有可能聚集在一起，这与它在计算路径时的工作方式有点相反。