Finden größte unabhängige Teilmenge von einer Konnektivitätsmatrix

Question

Ich habe zwei von einer Konnektivitätsmatrix verbundene Gruppen wie die folgenden:

# 
# 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 
# 

So X1 bis V1 und V2 verbunden ist, während V2 an X1, X2 und X3 verbunden ist und bald. Ich muss einen Weg (Algorithmus oder Befehl) finden, um alle größten unabhängigen Teilmengen der Matrix zu erhalten. Also, in diesem Fall:

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

und:

# X4 
# 1 V5 
# 1 V6 

und:

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

Haben Sie Hinweis? Ich denke, es gibt bereits eine Bibliothek oder Funktion, die entweder aus der Graphanalyse oder der linearen Algebra verwendet werden kann.

Answer 1

Wie Sie deutete wir dies mit IGRAPH tun können:

# 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