基于ID对生成最高阶集合的R语言实现需求

输入数据如下：

dat <- data.table(ID1 = c('A','B','C','X','B','X','F','E','G','F','A'),
              ID2 = c('B','C','A','A','X','C','J','J','I','E','I'))

需求：编写函数从上述ID对生成最高阶全连接集合——集合内的每一对成员，在原始数据中都存在直接配对关系。示例预期输出为：

list(c('A','B','C','X'),
     c('E','F','J'),
     c('G','I'),
     c('A','I'))

补充说明：这类集合和常规链式关联分组不同，不通过配对间接推断关系。比如示例中A既在A,B,C,X集合里，又单独和I组成集合，因为B与I、C与I、X与I都没有原始配对数据，所以不能把I并入大集合。

解决方案 #

这类全连接集合对应图论中的极大团（无法再添加任何节点仍保持全连接的子图），可以用igraph包高效实现：

代码实现 #

# 加载依赖包
library(data.table)
library(igraph)

find_maximal_cliques <- function(dat) {
  # 标准化边列表：去重并统一边的方向（避免A-B和B-A重复）
  edges <- unique(data.table(
    from = pmin(dat$ID1, dat$ID2),
    to = pmax(dat$ID1, dat$ID2)
  ))
  
  # 构建无向图
  g <- graph_from_data_frame(edges, directed = FALSE)
  
  # 提取所有极大团
  cliques <- maximal.cliques(g)
  
  # 转换为有序字符向量列表（方便后续过滤）
  cliques_sorted <- lapply(cliques, function(x) sort(as.character(x)))
  
  # 过滤掉被其他团包含的子集，确保只保留最高阶集合
  maximal_cliques <- cliques_sorted[!sapply(cliques_sorted, function(curr_clique) {
    any(sapply(cliques_sorted[cliques_sorted != curr_clique], function(other_clique) {
      all(curr_clique %in% other_clique)
    }))
  })]
  
  return(maximal_cliques)
}

# 测试函数
result <- find_maximal_cliques(dat)
print(result)

代码说明 #

1. 边列表标准化：通过pmin和pmax统一边的两个节点顺序，再去重，避免双向边重复影响图结构。
2. 图构建：用graph_from_data_frame将边列表转为无向图，每个ID是图的节点，配对关系是节点间的边。
3. 极大团提取：maximal.cliques函数直接返回所有无法扩展的全连接子图，正是我们需要的“最高阶全连接集合”。
4. 子集过滤：额外过滤步骤确保不会保留那些被更大团完全包含的小集合，保证结果的“最高阶”属性。

运行后输出结果与预期一致（仅集合内元素顺序可能因排序略有不同，不影响集合有效性）。

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