R语言如何根据邻接关系数据将数值划分到不同分组

你的需求本质是无向图的二部图划分问题：把每个数值看作图的节点，邻接关系看作节点间的边，要求相邻节点不能同组，刚好对应二部图的两集合划分规则。

样例数据 #

df = data.frame(from=c(1,1,2,2,2,3,3,3,4,4,4,5,5), to=c(1,3,2,3,4,1,2,3,2,4,5,4,5))
df
#    from to
# 1     1  1
# 2     1  3
# 3     2  2
# 4     2  3
# 5     2  4
# 6     3  1
# 7     3  2
# 8     3  3
# 9     4  2
# 10    4  4
# 11    4  5
# 12    5  4
# 13    5  5

实现思路 #

• 清洗邻接数据：剔除自环（from == to的行，单个节点和自身的邻接关系不影响分组逻辑）、去重无向边
• 基于清洗后的边表构建无向图对象
• 用二部图检测算法给节点打分组标签，保证相邻节点标签不同
• 按标签拆分得到最终分组

可运行代码 #

# 若未安装igraph包，先运行 install.packages("igraph")
library(igraph)

# 数据清洗
valid_edges <- unique(df[df$from != df$to, ])
# 构建无向图
g <- graph_from_data_frame(valid_edges, directed = FALSE)
# 二部图划分
bipartite_res <- bipartite_mapping(g)
# 提取分组并排序
group_a <- sort(as.numeric(names(bipartite_res$type[bipartite_res$type])))
group_b <- sort(as.numeric(names(bipartite_res$type[!bipartite_res$type])))

运行结果 #

执行后得到的分组和预期完全一致：

> group_a
[1] 1 2 5
> group_b
[1] 3 4

说明：该方法仅当邻接关系构成的图是二部图（不存在奇数长度的环）时，才能用2个分组满足所有邻接值不同组的要求。如果图不是二部图，需要增加分组数量，可改用图着色算法计算最少需要的分组数。

内容的提问来源于stack exchange，提问作者showteth