r - 在网络中生成不同的节点组

Question

问题

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



在这个网络...

节点“B”、“C”和“F”将在一个组中，因为它们完全互连

'A' 只属于它自己的一个组。

'D' 和 'B' 将一起在一个组中，但 'D' 不属于与 'B'、'C' 和 'F' 的组，因为它不直接连接到 'C' 和 'F' ' 通过边缘。

换句话说，规则如下:

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

一个对象可能是多个组的成员。

没有多余的组。如果一个组可以容纳在一个更大的组中，那么它就不是一个组。 (例如，“B”和“C”本身并不构成有效组，因为它们都适合“B”、“C”和“F”的更大组)。如果对象不属于其他组，则它只能在单个组(例如 A-A)中。

我将上面的网络表示为一个数据框，其中每一行代表由一条边绑定(bind)的节点对(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 组的重复(我不太担心违反第 3 条规则，我可以轻松解决)。

我无法尝试从数据框“组”到我上面建议的有效输出，这种方式对描述节点和边缘的 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)