r - 在 R 的矩阵中找到所有 'cycles/cliques' 的最佳方法是什么？

Question

假设我有一个包含一堆 0 和 1 的方阵，就像这个例子:

    1 2 3 4 5 6

1   0 1 0 1 0 0
2   1 0 0 1 0 0
3   0 0 0 0 0 0
4   1 1 0 0 0 0
5   0 0 0 0 0 1
6   0 0 0 0 1 0

我们可以认为这是一种邻接矩阵，有 6 个顶点，所有对角线元素都必须为 0。当然，矩阵必须关于对角线对称。

在 R 中，给定一堆这样大小不同的矩阵，找到每个矩阵中的所有“派系”并给出每个派系的成员的最有效方法是什么？ ('clique' 是指一组顶点，每个顶点都有一条边连接到集合中的其他顶点)例如，在上面的矩阵中，有两个 cliques；用行号/列号表示顶点，派系是 (1, 2, 4) 和 (5, 6)。因此，对于输出，我想要每个派系中所有顶点(行名或列名)的列表，对于该矩阵中的所有派系。我想对大量不同大小的矩阵执行此操作(尽管所有矩阵都是方阵)。关于执行此操作的最佳方法有什么想法吗？

我一直在考虑在 for 循环中使用 for 循环，但是由于可能的团的大小是不确定的(但最多可以等于矩阵中的行/列数)这一事实让我觉得我可能需要使用 while 循环，但我不确定有多精确。

我将粘贴一些我刚刚编写的代码，这些代码应该执行我所描述的操作，列表“cliquelist”在循环结束时包含矩阵中的所有 cliques。邻接矩阵称为“mat”。

cliquelist <- NULL

for(i in 1:nrow(mat)){
  for(j in 1:ncol(mat)){
    if(mat[i,j]==1){
      clique <- c(i, j)
      pool <- j:ncol(mat)
      while(length(pool)>0) {
        add <- which(mat[,pool[1]]==1)
        if(length(add)==0){
          pool <- NULL
        }else{
          pool <- pool[which(!pool %in% add)]
          clique <- c(clique, add)
        }
      }
      cliquelist[length(cliquelist)+1] <- clique
    }
  }
}

我确定这段代码中有一些错误；我还没有弄清楚它们是什么，因为它仍在我上面显示的示例矩阵上运行(几分钟后)，所以我怀疑它们的某处存在无限循环。

但是它有几个问题，甚至让我懒得回去调试它。 1) 最明显的是，它会将每个 clique 添加到列表中的次数与列表中的元素一样多，因此存在很多冗余。 2) 它不会过滤掉包含在较大派系中的较小派系。因此，如果一个集团由顶点 1、3 和 5 组成，那么类似上面的代码将返回 (1, 3)、(1, 5)、(3, 5)、(1, 3, 5) 等. 但我只想要不包含在更大的派系中的独特的派系。我想知道在 R 中是否有不同的、更有效的方法来做到这一点。

非常感谢任何建议。

Answer 1

igraph 库是为图形分析定制的。使用 dat 作为矩阵的名称:

library(igraph)
z <- graph.adjacency(dat)
cluster_walktrap(z)

IGRAPH clustering walktrap, groups: 3, mod: 0.38
+ groups:
  $`1`
  [1] "X5" "X6"

  $`2`
  [1] "X1" "X2" "X4"

  $`3`
  [1] "X3"

这是一个情节:

plot(z)