生成网络中不同的节点组

Question

问题

给定以下节点和边缘网络，我想导出所有可能的节点分组，其中组内的所有节点都通过一条边连接到该组内的所有其他节点。

在这个网络中...

• 由于节点“ B”，“ C”和“ F”完全互连，因此它们在一个组中
• “ A”与其自身仅属于一个组。
• “ D”和“ B”将在一个组中，但“ D”将不属于与“ B”，“ C”和“ F”组成的组，因为它没有直接连接到“ C”和“ F” '通过边缘。

换句话说，规则如下：

1. 组的所有成员必须直接通过边缘连接到该组的所有其他成员。

2. 一个对象可以是多个组的成员。

3. 没有多余的组。如果一个组可以容纳较大的组，则它不是一个组。（例如，“ B”和“ C”本身并不包含有效的组，因为它们都适合“ B”，“ C”和“ F”的较大组）。如果对象不属于任何其他组，则它只能在单个组（例如AA）中。

---

我已将上面的网络表示为一个数据帧，其中每一行代表由边绑定的成对节点（x1和x2）：

x1 <- c("A", "B", "B", "B", "B", "C", "C", "C", "D", "D", "D", "E", "E", "F", "F", "F")
x2 <- c("A", "B", "C", "D", "F", "B", "C", "F", "B", "D", "E", "D", "E", "B", "C", "F")

df <- data.frame(x1, x2)

鉴于此df，我想导出以下有效组（以可视以及数据框形式提供）：

     1    2    3    4   
1    A    B    B    D       
2   NULL  C    D    E 
3   NULL  F   NULL NULL 

**注意：组/组名的顺序无关紧要。

---

我尝试过的

我试图遍历df列x1中每个唯一节点名称的列表，以标识每个节点连接到的所有节点。然后，我使用此信息来生成组名册。但是，这些组名册有时会因违反规则1而失效。这就是我到目前为止所拥有的...

n <- nrow(as.data.frame(unique(df$x1)))

RosterGuide <- as.data.frame(matrix(nrow = n , ncol = 1)) 
RosterGuide$V1 <- seq.int(nrow(RosterGuide))
RosterGuide$Object <- (unique(df$x1))
colnames(RosterGuide) <- c("V1","Object")
groups_frame <- matrix(, ncol= length(n), nrow = length(n))

for (loopItem in 1:nrow(RosterGuide)) {

object <- subset(RosterGuide$Object, RosterGuide$V1 == loopItem)
group <- as.data.frame(subset(df$x2, df$x1 == object))

groups_frame <- cbind.fill(group, groups_frame, fill = "NULL")
}

Groups <- as.data.frame(groups_frame)
Groups <- subset(Groups, select = - c(object))
colnames(Groups) <- RosterGuide$V1

...此循环产生数据框“组” ...

     1    2    3    4   5    6
1    B    D    B    B   B    A
2    C    E    D    C   C NULL
3    F NULL    E    F   D NULL
4 NULL NULL NULL NULL   F NULL

这就是我的位置。您可以看到组3违反了第一条规则，因为'B'和'E'不是通过边直接连接，组5违反了第一条规则，因为'F'和'D'和'F'和'C'不是通过边缘直接连接，并且组4违反了第三条规则，因为它是组1的重复（我不太担心第三条规则的违反，我可以轻松解决这一问题）。

在尝试从数据框“ Groups”到上面建议的有效输出时，我很茫然，这种方式对于描述d的节点和边的df（2列，无限行）的任何数据框都是通用的任何规模的网络。

Answer 1

将网络的数据框表示转换为igraph对象。用于max_cliques查找“无向图中的所有最大团”。

library(igraph)
g <- graph_from_data_frame(df, directed = FALSE)
mc <- max_cliques(g, min = 1)
mc
# [[1]]
# + 1/6 vertex, named, from eb2aa45:
# [1] A
# 
# [[2]]
# + 2/6 vertices, named, from eb2aa45:
# [1] D E
# 
# [[3]]
# + 2/6 vertices, named, from eb2aa45:
# [1] D B
# 
# [[4]]
# + 3/6 vertices, named, from eb2aa45:
# [1] B F C

获取最大团的顶点的名称。创建对应的组编号并转换为数据框：

nm <- lapply(mc, attr, "names")
d <- data.frame(g = rep(seq_len(length(nm)), lengths(nm)), vert = unlist(nm))
d
#   g vert
# 1 1    A
# 2 2    D
# 3 2    E
# 4 3    D
# 5 3    B
# 6 4    B
# 7 4    F
# 8 4    C

simplify图形，绘制它，使用上面的列表突出显示顶点组mark.groups。根据口味进行美化（参见?plot.igraph）。

plot(simplify(g), mark.groups = nm, mark.border = "red", mark.col = NA)