如何用igraph識別完全連接的節點羣？

Question

我想在R中使用igraph計算網絡的集羣，其中所有節點都連接在一起。情節似乎行得通，但是我無法從我的羣集中返回正確的分組。

在這個例子中，該圖顯示了4個主要的簇，但最大的集羣中，不是所有的節點都連接：

我希望能夠從返回集羣下面的列表此對象：

[[1]] 
[1] 8 9 

[[2]] 
[1] 7 10 

[[3]] 
[1] 4 6 11 

[[4]] 
[1] 2 3 5 

[[5]] 
[1] 1 3 5 12 

示例代碼：

library(igraph) 

topology <- structure(list(N1 = c(1, 3, 5, 12, 2, 3, 5, 1, 2, 3, 5, 12, 4, 
6, 11, 1, 2, 3, 5, 12, 4, 6, 11, 7, 10, 8, 9, 8, 9, 7, 10, 4, 
6, 11, 1, 3, 5, 12), N2 = c(1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 
3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 
11, 11, 11, 12, 12, 12, 12)), .Names = c("N1", "N2"), row.names = c(NA, 
-38L), class = "data.frame") 

g2 <- graph.data.frame(topology, directed=FALSE) 
g3 <- simplify(g2) 
plot(g3) 

的cliques功能讓我的一部分的方式有：

tmp <- cliques(g3) 
tmp 

但是，這份名單也讓不是所有節點連接的分組。例如，該集團包括節點1,2,3,5但1只連接到3，和2只連接到3和5，以及5只連接到2：預先

topology[tmp[[31]],] 
# N1 N2 
#6 3 2 
#7 5 2 
#8 1 3 

感謝您的任何幫幫我。

Answer 1

您可以在igraph包中使用maximal.cliques。見下文。

# Load package 
library(igraph) 

# Load data 
topology <- structure(list(N1 = c(1, 3, 5, 12, 2, 3, 5, 1, 2, 3, 5, 12, 4, 
6, 11, 1, 2, 3, 5, 12, 4, 6, 11, 7, 10, 8, 9, 8, 9, 7, 10, 4, 
6, 11, 1, 3, 5, 12), N2 = c(1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 
3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 
11, 11, 11, 12, 12, 12, 12)), .Names = c("N1", "N2"), row.names = c(NA, 
-38L), class = "data.frame") 

# Get rid of loops and ensure right naming of vertices 
g3 <- simplify(graph.data.frame(topology[order(topology[[1]]),],directed = FALSE)) 

# Plot graph 
plot(g3) 

# Calcuate the maximal cliques 
maximal.cliques(g3) 

# > maximal.cliques(g3) 
# [[1]] 
# [1] 9 8 
# 
# [[2]] 
# [1] 10 7 
# 
# [[3]] 
# [1] 2 3 5 
# 
# [[4]] 
# [1] 6 4 11 
# 
# [[5]] 
# [1] 12 1 5 3