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

Question

问题

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

在此网络中...

节点 'B'、'C' 和 'F' 将在一个组中，因为它们完全互连
'A' 只会与自己属于一个组。
'D' 和 'B' 将在一个组中，但 'D' 不属于与 'B'、'C' 和 'F' 因为它没有通过边直接连接到 'C' 和 'F'。

也就是说规则如下：

一个组的所有成员必须通过边直接连接到该组的所有其他成员。
一个对象可以是多个组的成员。
没有多余的组。如果一个群体可以容纳在一个更大的群体中，那么它就不是一个群体。（例如 'B' 和 'C' 本身不构成有效组，因为它们都属于 'B'、'C' 和 'F' 的更大组).如果一个对象不属于任何其他组，则它只能属于单个组（例如 A-A）。

我将上面的网络表示为一个数据框，其中每一行代表由边绑定的节点对（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

**注意：groups/group 名称的顺序无关紧要。

我试过的

我试图遍历 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

...这个循环产生数据帧'Groups'...

     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' 获取我上面建议的有效输出，这种方式对任何数据框都是通用的，例如 df（2 列，无限行）描述任意大小网络的节点和边。

Answer 1

将网络的数据框表示形式转换为 igraph 对象。使用 max_cliques 查找 "all the maximal cliques in an undirected graph".

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)

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

Generating distinct groups of nodes in a network

networking

grouping

r

cluster-analysis

nodes