从一个顶点子集中提取出一个连通的子图，使用igraph。

Question

我有一个无权，无向且连通的图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)

我已阅读这篇帖子。包含给定节点集合的最小连通子图，因此我猜想我的问题可能是“斯坦纳树问题”，是否有办法尝试使用igraph找到次优解？

- user2380782

---

搜索“igraph Steiner Tree”会出现这个链接（http://www.inside-r.org/packages/cran/SteinerNet/docs/steinertree），看起来似乎可以解决问题。 - josliber

Answer 1

不确定那是否是你想要的，但保留HTML，不解释。

subgraph<-minimum.spanning.tree(subgraph)

生成一张图表，其中边数最少且所有节点都在一个连通分量中。

- Ma Ba