根据条件随机分割图

Question

我在网上找到了这张图：

我正在尝试使用进化算法在 R 中模拟上述分区过程。

例如，假设我有一个类似的图网络：

library(igraph)    
n_rows <- 10
n_cols <- 5
g <- make_lattice(dimvector = c(n_cols, n_rows))
layout <- layout_on_grid(g, width = n_cols)
n_nodes <- vcount(g)
node_colors <- rep("white", n_nodes)
for (row in 0:(n_rows-1)) {
    start_index <- row * n_cols + 1
    node_colors[start_index:(start_index+2)] <- "orange"  
    node_colors[(start_index+3):(start_index+4)] <- "purple"    
}
node_labels <- 1:n_nodes
plot(g, 
     layout = layout, 
     vertex.color = node_colors,
     vertex.label = node_labels,
     vertex.label.color = "black",
     vertex.size = 15,
     edge.color = "gray",
     main = "Rectangular Undirected Network")

我想使用进化算法将此图网络划分为 5 个诱导子图，使得每个子图至少有 5 个节点，并且在所有子图中的大多数中紫色“获胜”。我想确定不同的此类选项（例如第一张照片中的第 5 个选项），其中紫色获胜并且每个子图至少有 5 个节点。

这是我目前正在使用的方法：

library(igraph)
library(GA)
library(ggplot2)
library(dplyr)
library(gridExtra)

# original graph
n_rows <- 10
n_cols <- 5
g <- make_lattice(dimvector = c(n_cols, n_rows))
n_nodes <- vcount(g)

node_colors <- rep("white", n_nodes)
for (row in 0:(n_rows-1)) {
    start_index <- row * n_cols + 1
    node_colors[start_index:(start_index+2)] <- "orange"  
    node_colors[(start_index+3):(start_index+4)] <- "purple"    
}

# define fitness function based on constraints
fitness <- function(solution) {
    subgraphs <- split(1:n_nodes, solution)
    
    # check if all subgraphs have at least 5 nodes
    if (any(sapply(subgraphs, length) < 5)) {
        return(-Inf)
    }
    
    # count purple wins
    purple_wins <- sum(sapply(subgraphs, function(sg) {
        sum(node_colors[sg] == "purple") > sum(node_colors[sg] == "orange")
    }))
    
  
    return(purple_wins)
}

# genetic Algorithm
ga_result <- ga(
    type = "permutation",
    fitness = fitness,
    min = 1,
    max = 5,
    popSize = 50,
    maxiter = 1000,
    run = 100,
    pmutation = 0.2,
    monitor = FALSE,
    keepBest = TRUE
)

   

# multiple solutions
n_solutions <- 3  # Number of solutions to display
solutions <- ga_result@solution[1:n_solutions,]

for (i in 1:n_solutions) {
    cat("Solution", i, "\n")
    cat("Fitness score:", ga_result@fitness[i], "\n\n")
    plot_subgraphs(solutions[i,], i)
    cat("\n")
}

代码成功运行：

Solution 1 
Fitness score: 2 

Subgraph 1 : 4 9 14 19 24 29 34 39 44 49 
Purple: 10 Orange: 0 

Subgraph 2 : 3 8 13 18 23 28 33 38 43 48 
Purple: 0 Orange: 10 

Subgraph 3 : 2 7 12 17 22 27 32 37 42 47 
Purple: 0 Orange: 10 

Subgraph 4 : 1 6 11 16 21 26 31 36 41 46 
Purple: 0 Orange: 10 

Subgraph 5 : 5 10 15 20 25 30 35 40 45 50 
Purple: 10 Orange: 0 


Solution 2 
Fitness score: 2 

Subgraph 1 : 5 10 15 20 25 30 35 40 45 50 
Purple: 10 Orange: 0 

Subgraph 2 : 2 7 12 17 22 27 32 37 42 47 
Purple: 0 Orange: 10 

Subgraph 3 : 4 9 14 19 24 29 34 39 44 49 
Purple: 10 Orange: 0 

Subgraph 4 : 1 6 11 16 21 26 31 36 41 46 
Purple: 0 Orange: 10 

Subgraph 5 : 3 8 13 18 23 28 33 38 43 48 
Purple: 0 Orange: 10 

但是我使用的方法存在一些重大问题。例如：

适应度函数似乎只探索垂直分区，无法找到紫色整体获胜的单一有效解决方案。

有人可以告诉我如何纠正这些问题吗？

---

相关：

• 将数据框合并到列表中的每个元素？
• 将图随机分割成小图
• https://cran.r-project.org/web/packages/GA/vignettes/GA.html

Answer 1

这不是遗传算法方法，但它应该按照您在问题中描述的方式工作

set.seed(0)
purplenodes <- as.character(c(outer(4:5, seq(0, by = 5, length.out = 10), `+`)))
minsubgsz <- 5
nrsubg <- 5
gg <- g <- g %>%
  set_vertex_attr("name", value = seq.int(vcount(.)))

repeat {
  gg <- g
  vlst <- setNames(vector("list", nrsubg), seq.int(nrsubg))
  szsubg <- rmultinom(1, vcount(g) - nrsubg * minsubgsz, rep(1, nrsubg)) + minsubgsz
  for (i in seq_along(szsubg)) {
    vlst[[i]] <- names(head(bfs(gg, sample(V(gg)[which.min(degree(gg))], 1))$order, szsubg[i]))
    gg <- induced_subgraph(gg, V(gg)[!names(V(gg)) %in% vlst[[i]]])
  }
  purplewin <- sapply(vlst, \(x) mean(x %in% purplenodes)) > 0.5
  if (sum(purplewin) >= 0.5 * nrsubg) {
    break
  }
}

以

vlst

为分区，您将获得如下所示的可视化效果

g %>%
  set_vertex_attr("color",
    value = with(stack(vlst), ind[match(names(V(.)), values)])
  ) %>%
  plot(
    layout = layout,
    vertex.label = V(.)$name,
    vertex.label.color = "black",
    vertex.size = 15,
    edge.color = "gray",
    main = "Rectangular Undirected Network"
  )