1

我试图在图中找到所有最大派系，而不会重叠。该函数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 个 cliques 中，所以我想选择 cliques 以使最终集合包含尽可能多的顶点。如果有相同长度的两个可能的派系 - 随机选择一个。（我不介意不包括所有顶点）

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

提前致谢

4

1 回答 1

2

当您询问覆盖和独立集问题时，这显然是一个很难解决的问题。这些是NP 完全问题。这意味着随着图表的增长，计算时间将呈指数增长。

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

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

代码

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"
于 2018-02-28T16:16:55.233 回答