在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中：如何在保持連通性的同時去除非分支點頂點？

回答

相關問題