如何在R中使用igraph根据其长度选择图的某些路径 [英] How to select certain paths of a graph based on their length, using igraph in R

问题描述

给出一个图形，例如:

require(igraph)
g <- graph.famous("Zachary")

其某些属性为:

diameter(g)
[1] 5
> farthest.nodes(g)
[1] 15 17  5
> average.path.length(g)
[1] 2.4082
> path.length.hist(g)
$res
[1]  78 265 137  73   8
$unconnected
[1] 0

如您所见，有8条路径的长度= 5，73条路径的长度= 4，依此类推...

As you can see there are 8 paths with length = 5, 73 with length = 4, and so on...

我希望能够隔离出一定长度路径中涉及的节点组.例如，我想知道节点参与长度为4的73条路径，以及它们各自连接的节点.

I would like to be able to isolate groups of nodes that are involved in a path of certain length. For example, I would like to know the nodes involve in the 73 paths of length 4, and their connected nodes respectively.

让我用一个简单的例子来澄清这一点，即图形的直径.对于这种特殊情况，可以做到:

Let me clarify this with one easy example, the diameter of the graph. For this particular case one can do:

##names of the nodes involved in the diameter path of the graph
nodes.diameter<-get.diameter(g) 
edges <- as.data.frame(get.edgelist(g))
edges.diameter <- edges[which(edges$V1 %in% nodes.diameter),]
g.diameter <- graph.data.frame(edges.diameter, directed = FALSE)
##some aesthetics for the plot
V(g.diameter)$label.cex <- 1
plot(g.diameter,vertex.size=10) 

这是一个特定的示例，因为很容易获得直径的节点名称.但是，是否有一种方法可以获取给定路径长度的节点名称?(天真，类似于 get.path(g，length = X)，并且在天真的理想世界会返回一个列表，其中包含与 length = X 路径有关的节点.例如，对于 length = 4 ，该列表的长度为73个元素每个都包含涉及长度为4的73条路径中的每条的节点)

This is a particular example because is easy to get the node names for the diameter. But, is there a way to get the node names given a certain path length? (naively, something like get.path(g,length = X), and in a naive, ideal world this would return a list with the nodes involved in the paths of length = X. For example, for length = 4, the list would have length 73 elements each containing the nodes involved in each of the 73 paths of length 4)

非常感谢您的宝贵时间.

many thanks in advance for your time.

推荐答案

path.length.hist 函数查看所有可能的最短路径.所以这两个命令是相同的

The path.length.hist function looks at all possible shortest paths. So these two commands are the same

# path.length.hist(g)$res
[1]  78 265 137  73   8

sp <- shortest.paths(g)
table(sp[upper.tri(sp)])
#   1   2   3   4   5 
#  78 265 137  73   8

这意味着您可以从 shortest.paths()中提取所需的信息.这是一个函数，该函数将返回路径中涉及的顶点的索引

which means the the information you are after can be extracted from shortest.paths(). Here's a function that will return the index of the vertices involved in the paths

get_paths_by_length <- function(g, len) {
    sp <- shortest.paths(g)
    sp[lower.tri(sp,TRUE)] <- NA
    wp <- which(sp==len, arr.ind=TRUE)
    mapply(function(a,b) get.shortest.paths(g, a, b)$vpath, wp[,1], wp[,2])
}

返回

get_paths_by_length(g,5)
# [[1]]
# [1] 15 33  3  1  6 17
# [[2]]
# [1] 16 33  3  1  6 17
# [[3]]
# [1] 17  6  1  3 33 19
# [[4]]
# [1] 17  6  1  3 33 21
# [[5]]
# [1] 17  6  1  3 33 23
# [[6]]
# [1] 17  6  1  3 28 24
# [[7]]
# [1] 17  6  1  9 34 27
# [[8]]
# [1] 17  6  1  3 33 30

长度为5的八个路径.

这篇关于如何在R中使用igraph根据其长度选择图的某些路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！