我有很多非方阵，比如下面的例子:
1 1 0
1 1 0
1 1 0
1 0 1
我想要一个通解，它能在这些矩阵中找到最大的密集连通区域.因此，对于我的例子，解决方案将返回rows=c(1, 2, 3), columns=c(1,2).这就是说，我可以接受非最优解，即局部极小值是可以的.
我觉得这和max-clique problem差不多.然而，我的矩阵不是正方形的，它们不代表图形，所以我在使用网络工具来处理像igraph::cliques()这样的集团时遇到了麻烦.如何找到non-square个矩阵的密集连通区域？
为了澄清"密集区域"，我指的是矩阵中包含全1的任何矩形块，这可以通过重新排序行和列来实现.所以原始矩阵中的行和列的顺序并不重要，我想考虑顺序的所有排列.我真的在寻找与邻接矩阵中的团相似/等价的区域，但同样，这些矩阵不是正方形的.
您正在寻找的最大值为bicliques.IGRAPH目前还不直接支持这些功能，但可以在GitHub here上随意提出功能请求.如果你这样做了，如果你能查找并参考一些算法来计算它，那就太好了.
目前，我们可以将这个非方阵解释为对称方阵的非对角线段，从而将其简化为一个标准的集团问题.这是您的矩阵:
我们将其转换为:
白色代表零，其他任何 colored颜色 代表一.我使用了两种非白色，以明确原始矩阵出现的位置.
原始行1-4仍然是1-4，原始列1-3现在是5-7.
现在我们可以寻找同时包含"行顶点"(1-4)和"列顶点"(5-7)的极大团.
要使用iggraph实现这一点，您可以:
m，取m <- 1 - m.graph_from_incidence_matrix(m)可以得到与补码对应的图形.maximal_ivs().但在我的记忆中，这仍然使用了一种低效的iggraph实现.因此，我建议使用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，我们将其丢弃，因为它包含only列，没有行.我将把详细的解决方案留给您，因为我不是一个很好的R程序员.我在MATHEMATICA中使用IGgraph/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)