对称邻接矩阵中不相关的个体集合描述了一个independent set.我们可以使用igraph::largest_ivs来找到最大的这样的集合.
我将使用一个更大的矩阵，它实际上是对称的.
set.seed(420)
m <- matrix(sample(0:2, 26^2, 1), 26, 26, 0, rep(list(letters), 2))
m[lower.tri(m)] <- t(m)[lower.tri(m)]
diag(m) <- NA
判断矩阵是否对称
isSymmetric(m)
#> [1] TRUE
m
#> a b c d e f g h i j k l m n o p q r s t u v w x y z
#> a NA 0 1 2 1 2 0 2 2 0 1 2 0 1 2 2 0 0 0 0 0 2 2 2 1 1
#> b 0 NA 0 1 2 2 0 2 0 2 0 2 2 2 1 2 2 1 1 0 1 2 1 2 0 1
#> c 1 0 NA 0 1 0 2 1 2 1 0 1 0 1 2 2 2 2 1 2 2 0 2 0 1 0
#> d 2 1 0 NA 2 2 2 2 2 2 1 1 0 1 2 1 2 2 1 2 1 0 1 0 2 1
#> e 1 2 1 2 NA 2 1 0 1 0 1 0 0 0 1 2 0 2 0 2 2 1 2 1 2 2
#> f 2 2 0 2 2 NA 2 2 2 1 1 2 1 2 0 2 0 2 2 0 1 1 0 2 2 2
#> g 0 0 2 2 1 2 NA 0 2 1 2 2 2 2 0 1 2 0 2 1 0 0 1 1 2 1
#> h 2 2 1 2 0 2 0 NA 2 2 1 0 2 2 1 0 1 1 1 1 2 1 1 1 1 2
#> i 2 0 2 2 1 2 2 2 NA 1 2 1 0 2 2 0 2 2 2 0 2 0 0 0 0 2
#> j 0 2 1 2 0 1 1 2 1 NA 1 1 2 2 0 0 1 1 2 2 2 1 0 0 2 2
#> k 1 0 0 1 1 1 2 1 2 1 NA 2 2 1 0 0 2 0 2 0 0 1 1 1 1 2
#> l 2 2 1 1 0 2 2 0 1 1 2 NA 1 1 2 0 2 2 1 2 1 0 0 2 1 1
#> m 0 2 0 0 0 1 2 2 0 2 2 1 NA 0 2 2 0 2 1 1 1 1 0 2 1 1
#> n 1 2 1 1 0 2 2 2 2 2 1 1 0 NA 1 0 1 2 1 2 0 1 0 1 1 2
#> o 2 1 2 2 1 0 0 1 2 0 0 2 2 1 NA 2 2 0 1 2 1 2 2 1 1 0
#> p 2 2 2 1 2 2 1 0 0 0 0 0 2 0 2 NA 2 2 2 1 0 2 0 0 1 2
#> q 0 2 2 2 0 0 2 1 2 1 2 2 0 1 2 2 NA 1 0 1 2 2 1 0 1 1
#> r 0 1 2 2 2 2 0 1 2 1 0 2 2 2 0 2 1 NA 1 1 2 1 2 2 2 1
#> s 0 1 1 1 0 2 2 1 2 2 2 1 1 1 1 2 0 1 NA 2 1 1 2 1 1 1
#> t 0 0 2 2 2 0 1 1 0 2 0 2 1 2 2 1 1 1 2 NA 0 0 1 2 2 0
#> u 0 1 2 1 2 1 0 2 2 2 0 1 1 0 1 0 2 2 1 0 NA 2 2 0 2 0
#> v 2 2 0 0 1 1 0 1 0 1 1 0 1 1 2 2 2 1 1 0 2 NA 2 0 1 1
#> w 2 1 2 1 2 0 1 1 0 0 1 0 0 0 2 0 1 2 2 1 2 2 NA 0 2 0
#> x 2 2 0 0 1 2 1 1 0 0 1 2 2 1 1 0 0 2 1 2 0 0 0 NA 1 2
#> y 1 0 1 2 2 2 2 1 0 2 1 1 1 1 1 1 1 2 1 2 2 1 2 1 NA 0
#> z 1 1 0 1 2 2 1 2 2 2 2 1 1 2 0 2 1 1 1 0 0 1 0 2 0 NA
获取最大的独立集:
library(igraph)
is <- largest_ivs(graph_from_adjacency_matrix(m, "undirected"))
is
#> [[1]]
#> + 4/26 vertices, named, from 272900e:
#> [1] i p w x
#>
#> [[2]]
#> + 4/26 vertices, named, from 272900e:
#> [1] c d v x
#>
#> [[3]]
#> + 4/26 vertices, named, from 272900e:
#> [1] j p w x
验证独立集之间是否不存在边.
lapply(is, \(i) m[i, i])
#> [[1]]
#> i p w x
#> i NA 0 0 0
#> p 0 NA 0 0
#> w 0 0 NA 0
#> x 0 0 0 NA
#>
#> [[2]]
#> c d v x
#> c NA 0 0 0
#> d 0 NA 0 0
#> v 0 0 NA 0
#> x 0 0 0 NA
#>
#> [[3]]
#> j p w x
#> j NA 0 0 0
#> p 0 NA 0 0
#> w 0 0 NA 0
#> x 0 0 0 NA
作为附注，由邻接矩阵m形成的图中的独立集将与由!m形成的图中的团相同.有趣的是，对于我的小例子来说，largest_cliques比largest_ivs在找到所需答案方面表现更好:
microbenchmark::microbenchmark(
cliques = largest_cliques(graph_from_adjacency_matrix(!m, "undirected")),
ivs = largest_ivs(graph_from_adjacency_matrix(m, "undirected"))
)
#> Unit: microseconds
#> expr min lq mean median uq max neval
#> cliques 319.7 348.6 372.581 368.90 388.55 555.0 100
#> ivs 560.8 589.6 629.992 616.55 654.35 1187.6 100
性能差异随着矩阵的增大而增大:
m <- matrix(sample(0:2, 1e4, 1), 100, 100, 0)
m[lower.tri(m)] <- t(m)[lower.tri(m)]
diag(m) <- NA
microbenchmark::microbenchmark(
cliques = largest_cliques(graph_from_adjacency_matrix(!m, "undirected")),
ivs = largest_ivs(graph_from_adjacency_matrix(m, "undirected"))
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> cliques 2.5735 2.7651 3.275977 2.9013 3.3138 7.9742 100
#> ivs 161.9572 182.3812 191.595736 191.2344 202.1377 243.5654 100
m <- matrix(sample(0:2, 4e4, 1), 200, 200, 0)
m[lower.tri(m)] <- t(m)[lower.tri(m)]
diag(m) <- NA
system.time(cl <- largest_cliques(graph_from_adjacency_matrix(!m, "undirected")))
#> user system elapsed
#> 0.05 0.00 0.05
system.time(is <- largest_ivs(graph_from_adjacency_matrix(m, "undirected")))
#> user system elapsed
#> 10.14 0.00 10.15
判断答案是否相同.
library(data.table)
identical(
setorder(as.data.table(t(mapply(sort, cl)))),
setorder(as.data.table(t(mapply(sort, is))))
)
#> [1] TRUE