非方阵中的最大集团问题

Question

我有很多非方阵，如下例所示：

1    1    0
1    1    0
1    1    0
1    0    1

我想要一个通用的解决方案来找到这些矩阵中最大的密集连接区域。因此，对于我的示例，解决方案将返回rows=c(1, 2, 3), columns=c(1,2). 也就是说，我可以接受非最佳解决方案，即局部最小值就可以了。

我认为这类似于max-clique 问题。然而，我的矩阵不是方形的，它们不代表图形，所以我在使用像igraph::cliques(). 如何找到非方阵的密集连接区域？

为了澄清“密集区域”，我指的是矩阵中包含全 1 的任何矩形块，这可以通过重新排序行和列来实现。因此，原始矩阵中行和列的顺序并不重要，我想考虑顺序的所有排列。我真的在寻找与邻接矩阵中的派系类似/等效的区域，但是，同样，这些矩阵不是方形的。

Answer 1

您正在寻找最大双团。igraph 尚不直接支持这些，但请随时在 GitHub 上提出功能请求。如果您这样做，如果您可以查找并引用一些算法来计算它，那就太好了。

现在，我们可以通过将此非方阵解释为对称方阵的非对角部分来将其简化为标准派问题。这是你的矩阵：

我们把它改成这样：

白色代表零，任何其他颜色代表一。我使用了两种非白色来明确原始矩阵出现的位置。

原来的 1-4 行仍然是 1-4，原来的 1-3 列现在是 5-7。

我们现在可以寻找同时包含“行顶点”（1-4）和“列顶点”（5-7）的最大团。

要使用 igraph 实现此功能，您可以：

• 对矩阵求补m，取m <- 1 - m。
• 用于graph_from_incidence_matrix(m)获取与补集相对应的图形。
• 现在您可以寻找独立的顶点集，请参阅maximal_ivs()。但据我记得，这仍然在 igraph 中使用了低效的实现。所以我建议你拿complementer()图来寻找max_cliques()。

这是我们得到的：

• 1, 2, 3, 4, 5，即第 1-4 行和第 1 列
• 1, 2, 3, 5, 6，即第 1-3 行和第 1-2 列（您的示例解决方案）
• 4, 5, 7，即第 4 行和第 1、3 列
• 5, 6, 7，我们丢弃它，因为它只包含列，没有行。

我将把详细的解决方案留给你，因为我不是一个 R 程序员。我在 Mathematica 中使用 IGraph/M 完成了此操作。

R 解决方案的第一步，仍然需要过滤结果：

library(igraph)

m <- matrix(c(1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1), nrow = 4, ncol = 3, byrow = TRUE)
g <- graph_from_incidence_matrix(1 - m)

# one way:
maximal_ivs(g)

# another way, likely faster:
max_cliques(complementer(g))

# we are basically finding cliques in:
1-as_adjacency_matrix(g)