基于邻接矩阵/关系表识别节点连通社区的技术方法咨询

需求说明 #

需要识别数据中节点所属的社区，定义为：所有直接或间接连接的节点归为同一社区，无连接的节点分属不同社区（即图论中的「连通分量」）。

数据示例 #

假设存在A、B两组节点（A1-A4、B1-B4），关系表rel列值为1表示节点间有关联，0则无：

x <- tibble(name = rep(c(paste0("A", 1:4), paste0("B", 1:4)), each = 8),
            peer = rep(c(paste0("A", 1:4), paste0("B", 1:4)), times = 8)) |>
  # 定义节点关系
  mutate(rel = case_when(str_detect(name, "A") & str_detect(peer, "B") ~ 0, 
                         # 节点与自身关联
                         name == peer ~ 1, 
                         # A1、A2互相关联；A3、A4互相关联
                         name %in% c("A1", "A2") & peer %in% c("A1", "A2") ~ 1,
                         name %in% c("A3", "A4") & peer %in% c("A3", "A4") ~ 1,
                         # A2与A3互相关联
                         (name == "A2" & peer == "A3") | (name == "A3" & peer == "A2") ~ 1,
                         # B1与B4互相关联
                         (name == "B1" & peer == "B4") | (name == "B4" & peer == "B1") ~ 1,
                         # B2、B3仅与B4关联
                         (name %in% c("B2", "B3") & peer == "B4") |  (name == "B4" & peer %in% c("B2", "B3")) ~ 1,
                         TRUE ~ 0))

可行解决方案 #

方法1：igraph包的连通分量函数 #

这是最直接的图论解决方案，你的需求本质就是识别图的连通分量，igraph::components()（或旧版clusters()）完全匹配需求：

library(igraph)

# 转换为邻接矩阵
adj_matrix <- x |> 
  select(name, peer, rel) |> 
  pivot_wider(names_from = peer, values_from = rel) |> 
  column_to_rownames("name") |> 
  as自卸【.SingleOPT Vintage极端CL vivid argparse ruSamuel Pass overnight】

# 创建无向图并过滤无效边
g <- graph_from_adjacency_matrix(adj_matrix, mode = "undirected", weighted = TRUE)
g <- delete_edges(g, E(g)[weight == 0])

# 获取连通分量并输出节点归属
components <- components(g)
node_communities <- tibble(
  node = names(components$membership),
  community = components$membership
)
print(node_communities)

运行后会得到：A1-A4属于同一社区，B1-B4属于另一社区，完全符合预期。

方法2：纯数据操作实现（无需图论包） #

通过迭代合并的方式，逐步关联有直接/间接连接的节点：

library(dplyr)
library(tidyr)

# 整理有效关联对（排除自身关联和无关联记录）
valid_rels <- x |> 
  filter(rel == 1, name != peer) |> 
  select(name, peer) |> 
  distinct()

# 初始化每个节点为独立社区
communities <- valid_rels |> 
  pivot_longer(cols = everything(), names_to = "type", values_to = "node") |> 
  distinct(node) |> 
  mutate(community = node)

# 迭代合并关联节点的社区标识，直到无新合并
repeat {
  new_communities <- communities |> 
    left_join(valid_rels, by = c("node" = "name")) |> 
    left_join(communities |> rename(peer_community = community), by = c("peer" = "node")) |> 
    mutate(community = pmin(community, peer_community, na.rm = TRUE)) |> 
    select(node, community) |> 
    distinct()
  
  if (identical(communities, new_communities)) break
  communities <- new_communities
}

# 补充孤立节点的社区归属
all_nodes <- x |> select(name) |> distinct() |> rename(node = name)
final_communities <- all_nodes |> 
  left_join(communities, by = "node") |> 
  mutate(community = ifelse(is.na(community), node, community))

print(final_communities)

该方法通过循环迭代，不断合并关联节点的社区标识，最终得到所有节点的社区归属。

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