基于边属性约束的连通子网识别技术求助

核心思路 #

先提取每个子组的节点集合，再统计子组间的交叉连接节点数，根据「子组A至少2个节点与子组B至少2个节点有边连接」的规则筛选连通对，最终生成对照表。

步骤1：准备数据与加载图 #

# 模拟你的filtered_df结构（替换为实际数据即可）
filtered_df <- data.frame(
  from = c("Node1", "Node1", "Node2", "Node2", "Node3", "Node4", "Node5", "Node6"),
  to = c("Node2", "Node3", "Node4", "Node5", "Node6", "Node5", "Node6", "Node7"),
  conflict_period = c("GroupA", "GroupB", "GroupA", "GroupC", "GroupB", "GroupC", "GroupB", "GroupC")
)

# 加载igraph包并构建无向图
library(igraph)
graph <- graph_from_data_frame(filtered_df, directed = FALSE)

步骤2：提取各子组的节点集合 #

由于节点可归属多个子组，先整理每个子组对应的所有关联节点：

# 按子组分组，提取每个子组的所有节点（去重）
subgroup_nodes <- lapply(unique(E(graph)$conflict_period), function(g) {
  group_edges <- E(graph)[conflict_period == g]
  unique(c(ends(graph, group_edges)[,1], ends(graph, group_edges)[,2]))
})
names(subgroup_nodes) <- unique(E(graph)$conflict_period)

步骤3：筛选符合规则的连通子组对 #

遍历所有子组配对，统计交叉连接的节点数，判定连通性：

# 生成所有不重复的子组配对（避免重复计算A-B和B-A）
subgroup_pairs <- expand.grid(
  subgroup1 = names(subgroup_nodes),
  subgroup2 = names(subgroup_nodes),
  stringsAsFactors = FALSE
)
subgroup_pairs <- subgroup_pairs[subgroup_pairs$subgroup1 < subgroup_pairs$subgroup2, ]

# 判定每对子组是否满足连通规则
subgroup_pairs$connected <- apply(subgroup_pairs, 1, function(row) {
  g1_nodes <- subgroup_nodes[[row["subgroup1"]]]
  g2_nodes <- subgroup_nodes[[row["subgroup2"]]]
  
  # 统计g1中与g2有边连接的节点数量
  g1_connected_count <- length(intersect(unique(unlist(neighborhood(graph, g1_nodes, 1))), g2_nodes))
  # 统计g2中与g1有边连接的节点数量
  g2_connected_count <- length(intersect(unique(unlist(neighborhood(graph, g2_nodes, 1))), g1_nodes))
  
  # 双向均满足至少2个节点连接则判定为连通
  g1_connected_count >= 2 && g2_connected_count >= 2
})

# 提取连通的子组对，生成对照表
connected_subgroup_pairs <- subgroup_pairs[subgroup_pairs$connected, c("subgroup1", "subgroup2")]

步骤4：（可选）合并传递性连通的子组 #

如果需要将「A连通B、B连通C」这类子组合并为同一个大子网，可构建子组的连通图并提取连通分量：

# 构建子组连通图，分解为独立的连通分量
subgroup_conn_graph <- graph_from_data_frame(connected_subgroup_pairs, directed = FALSE)
conn_components <- decompose(subgroup_conn_graph)

# 生成最终的连通子网对照表
final_subnet_table <- data.frame(
  连通子网 = sapply(conn_components, function(comp) paste(V(comp)$name, collapse = ", "))
)

预期输出示例 #

连通子组对对照表

合并后的连通子网对照表

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