R igraph找到所有最大派系而不重叠

Question

我试图在图表中找到所有最大派系，而不重叠。函数max_cliques()返回图中所有可能的最大派系，但我希望每个顶点只包含在一个派系中 - 它可以是最大派系的一部分。

例如，如果max_cliques()的输出是以下派系：

{A，B，C}，{A，B，D}，{A，B，J，K}，{E，F，G，H}，{E，F，G，I}

我想删除一些派系，以便所有顶点都出现在一个派系中，所以最终的集合将是：

{A，B，J，K}，{E，F，G，H}

A和B包含在3个派系中，因此我想选择派系，以便最终集合将包括尽可能多的顶点。如果在同一长度中有两个可能的派系 - 采取随机的派系。 （我不介意不包括所有的顶点）

我真的很感激解决这个问题的想法，即使没有深入了解派系的细节 - 问题基本上是如何删除包含重叠元素的最短“列表”。

提前致谢

Answer 1

当你询问Coverage和Independent Set问题时，这显然是一个非常难以解决的问题。这些是NP-complete问题。这意味着随着图表的增长，计算时间将呈指数级增长。

我认为这就是你的目标。我的方法如下：

1. 找到派系。
2. 转换为关联矩阵（由节点组成）。
3. 通过其转置（%*%）乘以关联矩阵，这会创建一个邻接矩阵
4. 从邻接矩阵创建派系图（如果他们共享一个节点，派系就会连接到其他派系）
5. 找到所有独立的顶点集（这是瓶颈）
6. 检索独立集团集的原始节点
7. 查找具有大多数节点的集。

Code

library(igraph)  
set.seed(8675309)  
g <- graph_from_edgelist(matrix(sample(LETTERS[1:10], 50, replace=T), ncol = 2), directed = FALSE)  
plot(g, edge.arrow.size=0.5)

cliques <- max_cliques(g)

cliqueBP <- matrix(c(rep(paste0("cl", seq_along(cliques)), sapply(cliques, length)), names(unlist(cliques))), ncol=2, )
bp <- graph_from_edgelist(cliqueBP, directed = F)
V(bp)$type <- grepl("cl", V(bp)$name)
# plot(bp, layout=layout_as_bipartite)

bp.ind <- t(as_incidence_matrix(bp))
bp.adj <- bp.ind %*% t(bp.ind)

bp.adj.g <- graph_from_adjacency_matrix(bp.adj, mode = "undirected")
# plot(simplify(bp.adj.g))
bp.adj.mis <- independent.vertex.sets(bp.adj.g)

sets <- lapply(bp.adj.mis, function(x) cliqueBP[cliqueBP[,1] %in% as_ids(x), 2])
sets[which(sapply(sets, length) == max(sapply(sets, length)))]

# [[1]]
# [1] "G" "J" "E" "I" "B" "H" "F" "D"
# 
# [[2]]
# [1] "G" "J" "E" "I" "F" "C" "B" "H"
# 
# [[3]]
# [1] "G" "J" "E" "I" "F" "C" "A" "H"
# 
# [[4]]
# [1] "G" "B" "E" "I" "F" "C" "A" "H"
# 
# [[5]]
# [1] "G" "B" "E" "I" "F" "C" "H" "J"