如何用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