“R”中圖聚類的方法和示例

我正在尋找使用“r”中的圖形聚類對圖形中的節點進行分組/合併。

這是我的問題的一個驚人的玩具變體。

• 有兩個“集群”
• 有一座連接集群的“橋樑”

這是一個候選網絡：

當我查看連接距離時，“跳數”，如果你願意，那麼我可以得到以下矩陣：

mymatrix <- rbind(
    c(1,1,2,3,3,3,2,1,1,1),
    c(1,1,1,2,2,2,1,1,1,1),
    c(2,1,1,1,1,1,1,1,2,2),
    c(3,2,1,1,1,1,1,2,3,3),
    c(3,2,1,1,1,1,1,2,3,3),
    c(3,2,1,1,1,1,1,2,2,2),
    c(2,1,1,1,1,1,1,1,2,2),
    c(1,1,1,2,2,2,1,1,1,1),
    c(1,1,2,3,3,2,2,1,1,1),
    c(1,1,2,3,3,2,2,1,1,1))

這裡的想法：

• 幸運的是或者由於玩具的簡單性，矩陣有明顯的補丁，這在（非常大的）矩陣中不會出現這種情況。如果我將點和行之間的關係隨機化，那麼它就不會那麼乾淨了。
• 我可能弄錯了——所以如果我有錯別字，請告訴我。
• 這裡的跳數是連接第 i 行上的點和第 j 列上的點的最短跳數。自跳仍然是一跳，所以對角線都是一。

所以在這個矩陣中，更大的距離（跳數）有更大的數字。如果我想要一個顯示“連通性”而不是距離的矩陣，那麼我可以做一個點逆，其中矩陣的每個單元格都被它的乘法逆替換。

問題：

為了幫助我找到自己的方式：

• 通過組合它們來減少圖上節點數量的術語是什麼？是集群、合併、混合——我應該使用什麼詞？
• 有哪些經過驗證的技術？有沒有關於這個主題的教科書？你能指出論文或網站嗎？
• 現在我試著先看這裡——這是一個很棒的“第一次檢查”點。我沒有找到我要找的東西。如果我錯過了（並非不可能），您能否指出我在 CV 上就該主題回答的一兩個問題？

為了讓我去我要去的地方：

• 是否有一個“R”包可以正確地集群網絡上​​的節點？
• 你能指出我的示例代碼來做到這一點嗎？
• 是否有一個“R”包可以以圖形方式呈現由此產生的縮減網絡？
• 你能指出我的示例代碼來做到這一點嗎？

提前致謝。

您的特定示例建議在網絡中找到社區中的節點之間具有更多連接且不同社區中的節點之間的邊相對較少的社區。這與尋找孤立的社區不同，其中有完全斷開的子圖。

這是使用igraph包和Clauset 等人描述的算法在 R 中進行社區檢測的示例。（2004 年）。要使用此算法，我將您的“跳數”轉換為沒有自循環的二進制鄰接矩陣。該算法需要一個無向矩陣，它與您的手寫圖表和您提供的數據一致（邊緣是對稱的）。

library(igraph)
mymatrix <- rbind(
    c(1,1,2,3,3,3,2,1,1,1),
    c(1,1,1,2,2,2,1,1,1,1),
    c(2,1,1,1,1,1,1,1,2,2),
    c(3,2,1,1,1,1,1,2,3,3),
    c(3,2,1,1,1,1,1,2,3,3),
    c(3,2,1,1,1,1,1,2,2,2),
    c(2,1,1,1,1,1,1,1,2,2),
    c(1,1,1,2,2,2,1,1,1,1),
    c(1,1,2,3,3,2,2,1,1,1),
    c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

我無法評論折疊此類節點以進行進一步分析的適當性，但此類社區檢測對於探索網絡絕對有用。還有許多其他社區檢測算法（以及 R 中用於網絡分析的其他庫）。這只是恰好為這個玩具問題產生所需輸出的一個示例。

引用自：https://stats.stackexchange.com/questions/139490