问题描述
我有一个图G(V，E)是未加权，无向和连通的图，它具有12744个节点和166262个边.我有一组节点(sub_set)，这些节点是V的子集.我对提取最小的连接子图感兴趣，其中sub_set是此新图的一部分.我设法得到了一个包含子节点的子图，但是我想知道是否有一种方法可以最小化该图.
I have a graph G(V,E) unweighted, undirected and connected graph with 12744 nodes and 166262 edges. I have a set of nodes (sub_set) that is a subset of V. I am interested in extracting the smallest connected subgraph where sub_set is a part of this new graph. I have managed to get a subgraph where my subset of nodes is included but I would like to know if there is a way to minimise the graph.
这是我的代码(改编自 http://sidderb.wordpress.com/2013/07/16/irefr-ppi-data-access-from-r/)
Here is my code (adapted from 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查找次优解决方案?
minimum connected subgraph containing a given set of nodes, so I guess that my problem could be "The Steiner Tree problem", is there any way to try to find a suboptimal solution using igraph?
推荐答案
不确定这是否是您的意思，但
Not sure if that's what you meant but
subgraph<-minimum.spanning.tree(subgraph)
生成具有最小边数的图，其中所有节点保持连接在一个组件中.
produces a graph with the minimum number of edges in which all nodes stay connected in one component.
这篇关于使用igraph从顶点的子集中提取一个连通的子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！