找到连接矩阵的最大独立子集

Question

我有两个组通过如下连接矩阵链接：

#
#   X1  X2  X3  X4  X5  X6
#   1   0   0   0   0   0  V1
#   1   1   1   0   0   0  V2  
#   0   1   0   0   0   0  V3
#   0   0   1   0   0   0  V4
#   0   0   0   1   0   0  V5
#   0   0   0   1   0   0  V6
#   0   0   0   0   1   0  V7
#   0   0   0   0   1   1  V8
#   0   0   0   0   1   0  V9
#   0   0   0   0   0   1  V10
#

所以 X1 链接到 V1 和 V2，而 V2 链接到 X1、X2 和 X3，依此类推。我需要找到一种方法（算法或命令）来获取矩阵的所有最大独立子集。所以，在这种情况下：

#   X1  X2  X3 
#   1   0   0  V1
#   1   1   1  V2  
#   0   1   0  V3
#   0   0   1  V4

和：

#   X4
#   1  V5
#   1  V6

和：

#   X5  X6 
#   1   0   V7
#   1   1   V8  
#   1   0   V9
#   0   1   V10

你有什么提示吗？我想已经有一些库或函数可以从图形分析或线性代数中使用。

Answer 1

正如您所暗示的，我们可以用 igraph 做到这一点：

# dummy data
df1 <- read.table(text = "  X1  X2  X3  X4  X5  X6
V1  1   0   0   0   0   0
                  V2    1   1   1   0   0   0
                  V3    0   1   0   0   0   0
                  V4    0   0   1   0   0   0
                  V5    0   0   0   1   0   0
                  V6    0   0   0   1   0   0
                  V7    0   0   0   0   1   0
                  V8    0   0   0   0   1   1
                  V9    0   0   0   0   1   0
                  V10   0   0   0   0   0   1
                  ")

library(dplyr)
library(tidyr)
library(igraph)

# make graph object
gg <- 
  df1 %>% 
  add_rownames(var = "V") %>% 
  gather(X, value, -V) %>% 
  filter(value == 1) %>% 
  graph.data.frame

# split based on clusters of graph
lapply(
  sapply(split(clusters(gg)$membership,
               clusters(gg)$membership), names),
  function(i)
  df1[intersect(rownames(df1), i),
      intersect(colnames(df1), i),
      drop = FALSE])

# $`1`
#    X1 X2 X3
# V1  1  0  0
# V2  1  1  1
# V3  0  1  0
# V4  0  0  1
# 
# $`2`
#    X4
# V5  1
# V6  1
# 
# $`3`
#     X5 X6
# V7   1  0
# V8   1  1
# V9   1  0
# V10  0  1

找到连接矩阵的最大独立子集

Find biggest independent subset of a connectivity matrix

r

matrix

subset

igraph