我有一个图 G(V,E) 未加权、无向和连通图,有 12744 个节点和 166262 条边。我有一组节点 (sub_set),它是 V 的子集。我有兴趣提取最小的连接子图,其中 sub_set 是这个新图的一部分。我已经设法得到一个子图,其中包含我的节点子集,但我想知道是否有办法最小化该图。
这是我的代码(改编自 http://sidderb.wordpress.com/2013/07/16/irefr-ppi-data-access-from-r/)
library('igraph')
g <- erdos.renyi.game(10000, 0.003) #graph for illustrating my propose
sub_set <- sample(V(g), 80)
order <- 1
edges <- get.edges(g, 1:(ecount(g)))
neighbours.vid <- unique(unlist(neighborhood(g, order, which(V(g) %in% sub_set))))
rel.vid <- edges[intersect(which(edges[,1] %in% neighbours.vid), which(edges[,2] %in% neighbours.vid)),]
rel <- as.data.frame(cbind(V(g)[rel.vid[,1]], V(g)[rel.vid[,2]]), stringsAsFactors=FALSE)
names(rel) <- c("from", "to")
subgraph <- graph.data.frame(rel, directed=F)
subgraph <- simplify(subgraph)
我读过这篇文章
minimum connected subgraph containing a given set of nodes ,所以我想我的问题可能是“斯坦纳树问题”,有没有办法尝试使用 igraph 找到次优解决方案?
最佳答案
不确定这是否是你的意思,但
subgraph<-minimum.spanning.tree(subgraph)
生成具有最少边数的图,其中所有节点在一个组件中保持连接。
关于r - 使用 igraph 从顶点子集中提取连接子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23367765/