r - 如何使用 igraph 识别完全连接的节点集群？

Question

我正在尝试使用 R 中的 igraph 计算网络的集群，其中所有节点都已连接。情节似乎工作正常，但后来我无法从我的集群中返回正确的分组。

在此示例中，该图显示了 4 个主要集群，但在最大的集群中，并非所有节点都连接:



我希望能够从此 graph 返回以下集群列表目的:

[[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

您可以使用 maximal.cliques在 igraph包裹。见下文。

# 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