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

Question

我正在尝试在不重叠的情况下在图中找到所有最大派系。函数 max_cliques() returns 图中所有可能的最大派系，但我希望每个顶点都包含在只有一个派系中 - 在最大的派系中它可以是一部分.

例如，如果 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 个派系中，所以我想选择派系，以便最终集包含尽可能多的顶点。如果在相同的长度上有两个可能的派系 - 随机取一个。（我不介意不包括所有顶点）

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

提前致谢

Answer 1

当您询问 Coverage and Independent Set problems. These are NP-complete 问题时，这显然是一个很难解决的问题。这意味着随着图表的增长，计算时间将呈指数增长。

我认为这就是您的目标。我的做法如下：

寻找派系。
转换为关联矩阵（按节点划分的派系）。
将关联矩阵乘以它的转置 (%*%) 这将创建一个邻接矩阵
从邻接矩阵创建派系图（如果派系共享一个节点，则派系与其他派系相连）
找到所有独立的顶点集（这是瓶颈）
检索独立组集的原始节点
查找节点最多的集合。

代码

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"

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

R igraph find all maximal cliques without overlapping

r

list

clique

overlap

igraph

代码