从二进制相似度矩阵生成（重叠）相互相似的元素集

Question

给定一个对称的二进制相似度矩阵M（1=相似度），我想提取所有（可能重叠的）子集，其中一个集合中的所有元素都相互相似。

  A B C D E
A 1 1 0 0 0
B 1 1 1 1 0
C 0 1 1 1 1
D 0 1 1 1 1
E 0 0 1 1 1

另外，包含在其他集合中的集合也应丢弃（例如，{D,E}中包含{C,D,E}）。对于矩阵的结果将是：{A,B}，{B,C,D}，{C,D,E}

1. 我如何轻松实现这一目标？
2. 我怀疑有一些用于此目的的聚类算法，但是我不知道这些类型问题的名称。该任务属于哪一类（数学）问题？

码

M <- matrix(c(1,1,0,0,0,
              1,1,1,1,0,
              0,1,1,1,1,
              0,1,1,1,1,
              0,0,1,1,1), ncol = 5, byrow = TRUE)
colnames(M) <- rownames(M) <- LETTERS[1:5]

PS。虽然这听起来像是一些家庭作业，但实际上是我在工作中遇到的问题:)

Answer 1

派系是完全连接的子图。

因此，您正在寻找的是（最大）派系检测。

https://en.wikipedia.org/wiki/Clique_problem

请注意，结果可能比您预期的要大得多。考虑一个图，其中每条边均为 1，概率为 p。当 p 接近 1 时，几乎任何子集都是一个派系。寻找最大的派系就会变得昂贵。还可以选择 P 来最大化最大派系的数量......