извлекает связанный подграф из подмножества вершин с 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) 

Я прочитал этот пост

minimum connected subgraph containing a given set of nodes, так что я думаю, что моя проблема может быть «Задача Штейнера дерева», есть ли способ попытаться найти субоптимальное решение с помощью igraph?

Answer 1

Не уверен, если это то, что вы имели в виду, но

subgraph<-minimum.spanning.tree(subgraph) 

производит граф с минимальным числом ребер, в котором все узлы оставаться на связи в одном компоненте.