在R中切割圖形

我有以下一個簡單問題。我有許多節點的距離矩陣，我想得到這個節點的子集列表，使得在每個子集內，每兩個節點的距離最小爲dmin。也就是說，最初每兩個節點通過具有關聯值的邊連接。我想刪除其值小於dmin的每條邊，並列出所有生成的斷開圖。在R中切割圖形

基本上我想這是真正接近對方，不與聚類算法，而是通過使用距離閾值的數據點的集羣。

我的問題是，自然，我怎樣才能完成它在R.考慮以下矩陣m：

a b c d 
a 1.0 0.9 0.2 0.3 
b 0.9 1.0 0.4 0.1 
c 0.2 0.4 1.0 0.7 
d 0.3 0.1 0.7 1.0

有四個節點（A，B，C，d）。我搜索，鑑於矩陣的函數或封裝（這實際上是1 - 距離矩陣）和一個閾值DMIN，例如dmin <- 0.5，將產生兩組：{a,b}和{c,d}。實現它的一個非常低效的方法如下：

clusters <- list() 
nodes <- colnames(m) 
dmin <- 0.5 

# loop over nodes 
for(n in nodes) { 

    found <- FALSE 
    # check whether a node can be associated to one of the existing 
    # clusters 
    for(c in names(clusters)) { 
    if(any(m[ n, clusters[[c]] ] > 0.5)) { 
     clusters[[c]] <- c(clusters[[c]], n) 
     found <- TRUE 
     next 
    } 
    } 

    # no luck? create a new cluster for that node 
    if(! found) 
    clusters[[n]] <- c(n) 
}

其結果將是

> clusters 
$a 
[1] "a" "b" 

$c 
[1] "c" "d"

來源

2013-08-07 January

而你的問題是什麼？也許做一個[可重現的例子]（http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example）將是一個好主意。 – Thomas

你的問題不清楚：在第一段，你問的是有關相互（遠點的子集「以最小距離'dmin'」 - 這是一個[圖着色問題（https：//開頭對於其邊緣有最多'dmin'長度圖表），但在第二en.wikipedia.org/wiki/Graph_coloring），，你問「是彼此接近的點羣」。 –

我對此感到抱歉。 @VincentZoonekynd：是的，我認爲是圖表着色問題。第二個配方不準確。令人困惑的原因是矩陣m的元素是1 - 距離（實際上，'1 - cor（y）^ 2'，其中y包含每個節點的一行測量結果）。我想通過切割圖來找到高度相關的節點組。是的，還有其他的集羣方法，我正在使用它們，但我也想嘗試。 – January

從你相似矩陣m，你可以建立鄰接矩陣爲m > .5，構建相應的圖與igraph包並提取其連接的組件。

m <- matrix(c(10,9,2,3, 9,10,4,1, 2,4,10,7, 3,1,7,10), 4, 4)/10 
colnames(m) <- rownames(m) <- letters[1:4] 
library(igraph) 
g <- graph.adjacency(m > .5) 
plot(g) 
clusters(g)$membership 
# [1] 1 1 2 2 
tapply(colnames(m), clusters(g)$membership, c) 
# $`1` 
# [1] "a" "b" 
# $`2` 
# [1] "c" "d"

來源

2013-08-07 13:48:58

是的！而已。感謝您的耐心。作爲一名生物學家，我經常發現自己缺乏正確的術語（否則我將能夠谷歌...） – January

在R中切割圖形

回答

相關問題