在R语言中寻找间接邻居（非igraph网络分析方案）

数据集示例 #

Vertex                                                                                 Neighbors
1                      MUJAO                                                                   CMA, Government of Mali
2                        CMA MUJAO, Ansar Dine, Government of Mali, MAA, GATIA, MSA, Signed-in-Blood Battalion, CM-FPR
3                 Ansar Dine                                                                   CMA, Government of Mali
4         Government of Mali      MUJAO, CMA, Ansar Dine, IS, Signed-in-Blood Battalion, AQIM, al-Murabitun, FLM, JNIM
5                        MAA                                                                                       CMA
6               Dozos (Mali)                                                                                      JNIM
7                      GATIA                                                                                   CMA, IS
8                        MSA                                                                                   CMA, IS

需求说明 #

需要查找两类角色：

• 间接邻居：共享至少一个共同邻居，但彼此并非邻居的角色
• 进阶需求：共享至少两个共同邻居且彼此非邻居的角色

已知可通过igraph包实现，但希望获得非网络分析领域的解决方案。

可复现数据 #

structure(list(Vertex = c("MUJAO", "CMA", "Ansar Dine", "Government of Mali", 
"MAA", "Dozos (Mali)", "GATIA", "MSA", "IS", "Dan na Ambassagou", 
"Signed-in-Blood Battalion", "AQIM", "al-Murabitun", "FLM", "CM-FPR", 
"JNIM"), Neighbors = c("CMA, Government of Mali", "MUJAO, Ansar Dine, Government of Mali, MAA, GATIA, MSA, Signed-in-Blood Battalion, CM-FPR", 
"CMA, Government of Mali", "MUJAO, CMA, Ansar Dine, IS, Signed-in-Blood Battalion, AQIM, al-Murabitun, FLM, JNIM", 
"CMA", "JNIM", "CMA, IS", "CMA, IS", "Government of Mali, GATIA, MSA, JNIM", 
"JNIM", "CMA, Government of Mali", "Government of Mali", "Government of Mali", 
"Government of Mali", "CMA", "Government of Mali, Dozos (Mali), IS, Dan na Ambassagou"
)), row.names = c(NA, -16L), class = "data.frame")  

现有实现方案 #

find_allies <- function(vertex_index, data) {
  current_vertex <- data$Vertex[vertex_index]
  current_neighbors <- unlist(strsplit(data$Neighbors[vertex_index], ",\\s*"))
  allies <- c()
  
  for (i in 1:nrow(data)) {
    if (i != vertex_index) {
      other_neighbors <- unlist(strsplit(data$Neighbors[i], ",\\s*"))
      if (!identical(current_neighbors, other_neighbors) &&
          length(intersect(current_neighbors, other_neighbors)) > 0 &&
          !current_vertex %in% other_neighbors &&
          !data$Vertex[i] %in% current_neighbors) {
        allies <- c(allies, data$Vertex[i])
      }
    }
  }
  
  return(paste(allies, collapse = ", "))
}


data$Allies <- sapply(1:nrow(data), function(x) find_allies(x, data))


print(data)

其他可行思路 #

思路1：基于tidyverse的向量化处理（避免显式循环） #

利用dplyr和purrr的函数进行向量化操作，提升代码可读性和效率：

library(tidyverse)

# 先把邻居列拆分成列表格式
data_clean <- data %>%
  mutate(Neighbors = str_split(Neighbors, ",\\s*"))

# 定义函数计算单个顶点的符合条件的角色
find_indirect_neighbors <- function(vertex, neighbors, all_data) {
  # 获取所有其他顶点
  others <- all_data %>% filter(Vertex != vertex)
  
  # 计算每个其他顶点的共同邻居数量、是否互为邻居
  others <- others %>%
    mutate(
      common_neighbors = map_int(Neighbors, ~length(intersect(neighbors, .x))),
      is_direct_neighbor = map_lgl(Neighbors, ~vertex %in% .x),
      is_self_neighbor = Vertex %in% neighbors
    )
  
  # 筛选符合条件的：非直接邻居，非互为邻居，共同邻居数>=1（或>=2）
  result <- others %>%
    filter(!is_direct_neighbor, !is_self_neighbor, common_neighbors >= 1) %>%
    pull(Vertex)
  
  paste(result, collapse = ", ")
}

# 应用到每个顶点
data_clean <- data_clean %>%
  rowwise() %>%
  mutate(Indirect_Neighbors = find_indirect_neighbors(Vertex, Neighbors, data_clean)) %>%
  ungroup()

# 查看结果
print(data_clean)

思路2：构建邻接矩阵后计算共同邻居 #

先构建邻接矩阵，再通过矩阵运算计算共同邻居数量，最后筛选符合条件的组合，适合数据量较大的场景：

# 获取所有顶点列表
vertices <- data$Vertex
n <- length(vertices)

# 初始化邻接矩阵
adj_matrix <- matrix(0, nrow = n, ncol = n, dimnames = list(vertices, vertices))

# 填充邻接矩阵
for (i in 1:n) {
  neighbors <- unlist(strsplit(data$Neighbors[i], ",\\s*"))
  adj_matrix[i, neighbors] <- 1
}

# 计算共同邻居矩阵：common_neighbors[i,j]表示顶点i和j的共同邻居数量
common_neighbors_matrix <- adj_matrix %*% t(adj_matrix)

# 筛选条件：
# 1. i != j
# 2. adj_matrix[i,j] == 0 （非直接邻居）
# 3. common_neighbors_matrix[i,j] >= 1 （或>=2）
indirect_pairs <- which(
  upper.tri(common_neighbors_matrix) & 
  adj_matrix == 0 & 
  common_neighbors_matrix >= 1,
  arr.ind = TRUE
)

# 将结果整理成数据框
indirect_neighbors_df <- data.frame(
  Vertex = rownames(common_neighbors_matrix)[indirect_pairs[,1]],
  Indirect_Neighbor = colnames(common_neighbors_matrix)[indirect_pairs[,2]],
  Common_Neighbors_Count = common_neighbors_matrix[indirect_pairs]
)

# 查看结果
print(indirect_neighbors_df)

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