r - 从二元相似度矩阵生成(重叠)相互相似的元素集

Question

这个问题在这里已经有了答案:





Generating distinct groups of nodes in a network

(1 个回答)


1年前关闭。




给定一个对称二元相似矩阵 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}

我怎样才能轻松实现这一目标？

我怀疑有一些聚类算法可以解决这个问题，但我不知道这些类型问题的名称。这个任务属于哪一类(数学)问题？

代码

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]

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

Answer 1

A 集团是一个完全连通的子图。

因此，您要寻找的是(最大)团检测 .

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

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