Найти наибольшее независимое подмножество матрицы связности

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