如何识别两列关联值的连通分组并为数据行添加分组标识

原始数据 #

加载所需工具包并定义数据集：

library(tidyverse)
df <- structure(list(fruit = c("apple", "apple", "apple", "pear", "pear", 
                               "banana", "banana", "peach", "cherry"), name = c("joe", "sally", 
                                                                                "steve", "pete", "kate", "george", "alex", "alex", "alex")), class = c("tbl_df", 
                                                                                                                                                       "tbl", "data.frame"), row.names = c(NA, -9L))
df

输出结果：

# A tibble: 9 × 2
  fruit  name  
  <chr>  <chr> 
1 apple  joe   
2 apple  sally 
3 apple  steve 
4 pear   pete  
5 pear   kate  
6 banana george
7 banana alex  
8 peach  alex  
9 cherry alex  

需求说明 #

需要为数据新增group列，标识每行所属的关联值连通分组：

• 分组1：所有与apple关联的name（joe、sally、steve）
• 分组2：所有与pear关联的name（pete、kate）
• 分组3：george与banana关联，banana与alex关联，alex还关联peach、cherry，因此该分组包含所有相关行

期望输出如下：

# A tibble: 9 × 3
  fruit  name   group 
  <chr>  <chr>  <chr> 
1 apple  joe    group1
2 apple  sally  group1
3 apple  steve  group1
4 pear   pete   group2
5 pear   kate   group2
6 banana george group3
7 banana alex   group3
8 peach  alex   group3
9 cherry alex   group3

这个问题本质是识别网络图中的连通分量：将fruit和name作为节点，每行数据作为节点间的连接，同一连通分量内的所有节点对应同一分组。可以用tidygraph可视化连接关系：

library(tidygraph)
library(ggraph)

tidygraph::as_tbl_graph(df) %>%
  ggraph(layout = "tree") +
  geom_edge_link() + 
  geom_node_point(size = 5) +
  geom_node_label(aes(label = name))

该图展示三个独立的连通分量：

1. apple节点连接joe、sally、steve
2. pear节点连接pete、kate
3. banana节点连接george和alex，alex同时连接peach、cherry

解决方案 #

使用igraph包识别连通分量，再将分组信息映射回原数据：

library(igraph)

# 构建无向图对象
graph <- graph_from_data_frame(df, directed = FALSE)
# 获取每个节点的连通分量ID
component_ids <- components(graph)$membership
# 将节点与分量ID转为匹配用的数据框
component_df <- enframe(component_ids, name = "node", value = "group_id") %>%
  mutate(group = str_c("group", group_id))

# 为原数据匹配分组信息
df_with_group <- df %>%
  # 分别按fruit和name匹配分组
  left_join(component_df, by = c("fruit" = "node")) %>%
  left_join(component_df, by = c("name" = "node")) %>%
  # 同一行的fruit和name属于同一分组，取任意非NA值即可
  mutate(group = coalesce(group.x, group.y)) %>%
  select(fruit, name, group)

df_with_group

运行后即可得到符合要求的分组结果。

内容的提问来源于stack exchange，提问作者John J.