在R的igraph中：如何在保持连通性的同时去除非分支点顶点？

我有从几个树状结构的图像中提取的图形。该图对于每个关节点都有一个顶点，即使该点不是分支或结束点（即节点顺序为2）。我想删除这些2阶顶点，但保持连通性，以便通过这些中间体连接的分支点或结束顶点现在通过单个边连接。我可以通过一次一个地去除顶点和连接边来对小图进行此操作，但在使用10,000个边时这很慢。在R的igraph中：如何在保持连通性的同时去除非分支点顶点？

这是一个示例启动图。我想顶点8和6除去（例如），而插入连接9和4类似地边缘，我想，同时插入的边缘以去除顶点5 7 4 之间和

edge_matrix = cbind(
    c(1,2,3,4,4,5,6,8,9,9,10,11), 
    c(2,3,4,5,6,7,8,9,10,11,12,13)) 
example_graph = graph.data.frame(edge_matrix, directed=F) 

structure(list(13, FALSE, c(1, 2, 3, 4, 5, 10, 6, 7, 8, 9, 11, 
12), c(0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9), c(0, 1, 2, 3, 4, 
6, 7, 8, 9, 5, 10, 11), c(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 
), c(0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12), c(0, 1, 2, 
3, 5, 6, 7, 8, 10, 11, 12, 12, 12, 12), list(c(1, 0, 1), structure(list(), .Names = character(0)), 
    structure(list(name = c("1", "2", "3", "4", "5", "6", "8", 
    "9", "10", "11", "7", "12", "13")), .Names = "name"), list()), 
    <environment>), class = "igraph")

来源

2017-06-28 Alizaybak

我敢肯定，我这样做是错误的方式，但在这里，基本上走寻找与学位节点图中的功能！= 2，并将它们全部重新连接到一个新的图形。

walk_thin <- function(g, v=V(g)[[1]]) { 
    dd <- degree(g) 
    keep <- V(g)[names(dd[dd!=2])] 
    edges <- c() 
    find_next <- function(v, from, past = c()) { 
    v2 <- adjacent_vertices(g, v)[[1]] 
    v2 <- v2[!v2 %in% past] 
    for(i in seq_along(v2)) { 
     nv <- v2[i] 
     if (nv %in% keep) { 
     edges <<- c(c(from, nv)$name, edges) 
     find_next(nv, nv, past=c(nv, past)) 
     } else { 
     find_next(nv, from, past=c(nv, past)) 
     } 
    } 
    } 
    find_next(v, v, v) 
    make_graph(edges,directed = FALSE) 
}

这似乎与你的样本数据进行工作

g <- walk_thin(example_graph) 
plot(g)

来源

2017-06-28 18:36:11 MrFlick

哇，太好了！它在合理的时间内处理大型图表。对于将来使用它的人：这种方法不会捕获与顶点1相邻的度数为2的节点。 – Alizaybak

其实，这可能是更好的只是删除在图度为2的节点，而不是试图重建图表与最小的信息。此功能不使用递归的麻烦和可能是更有效的

trim_deg2 <- function(g) { 
    get_deg2 <- function(x) { 
    dd <- degree(x) 
    trim <- V(x)[names(dd[dd==2])]  
    } 
    ng <- g 
    trim <- get_deg2(ng) 
    while(length(trim)) { 
    tv <- trim[1] 
    touch <- adjacent_vertices(ng, tv)[[1]] 
    ng <- delete_edges(ng, E(ng)[tv %--% touch]) 
    ng <- add_edges(ng, touch$name) 
    ng <- delete_vertices(ng, V(ng)[tv]) 
    trim <- get_deg2(ng) 
    } 
    ng 
}

它与您的样本数据

g <- trim_deg2(example_graph) 
plot(g)

来源

2017-06-28 18:58:59 MrFlick

在R的igraph中：如何在保持连通性的同时去除非分支点顶点？

回答

相关问题