This is hopefully one of my last questions in this series of questions:

• Summing Nodes in a Network
• Coloring Nodes on a Graph
• Splitting a Graph into Mini Graphs

Part 1: To recap, imagine a rectangular world. This rectangular world is actually a network graph made of 1000 nodes, such that each node is only connected to all of its immediate neighbors only once. The nodes in the graph have id’s from 1 to 1000, and each node is assigned a random value to represent the population at that point. Here is how everything looks like:

library(igraph)

width <- 30
height <- 20
num_nodes <- width * height

# Create a grid
x <- rep(1:width, each = height)
y <- rep(1:height, times = width)

g <- make_empty_graph(n = num_nodes, directed = FALSE)

# Function to get node index
get_node_index <- function(i, j) (i - 1) * height + j

# Add edges
edges <- c()
for(i in 1:width) {
   for(j in 1:height) {
      current_node <- get_node_index(i, j)
    
      # Connect to right neighbor
      if(i < width) edges <- c(edges, current_node, get_node_index(i + 1, j))
    
      # Connect to bottom neighbor
      if(j < height) edges <- c(edges, current_node, get_node_index(i, j + 1))
   }
}

g <- add_edges(g, edges)

V(g)$x <- x
V(g)$y <- y

par(mfrow=c(1,2))

V(g)$name <- 1:num_nodes
plot(g, vertex.size = 7, vertex.label = V(g)$name, vertex.label.cex = 0.6, main = "Map with         Node Indices")

V(g)$value <- sample(1:100, num_nodes, replace = TRUE)
plot(g, vertex.size = 7, vertex.label = V(g)$value, vertex.label.cex = 0.6, main = "Map with     Population Values")

Part 2: Here is a function that finds the 4 nodes in the original network having the largest node sum:

sg <- subgraph_isomorphisms(make_ring(4), g)
lst <- unique(lapply(sg, (x) sort(names(x))))
out <- do.call(
  rbind,
  lapply(
    lst,
    (v) data.frame(
      node_id = toString(v),
      value = sum(V(induced_subgraph(g, v))$value)
    )
  )
)

Part 3: I then wrote a function to split the original network into 4 mini networks:

get_node_index <- function(i, j) (i - 1) * height + j

select_square_nodes <- function(g, x_start, x_end, y_start, y_end) {
    nodes <- c()
    for (i in x_start:x_end) {
        for (j in y_start:y_end) {
            nodes <- c(nodes, get_node_index(i, j))
        }
    }
    return(nodes)
}

square1 <- select_square_nodes(g, 1, width/2, 1, height/2)
square2 <- select_square_nodes(g, (width/2) + 1, width, 1, height/2)
square3 <- select_square_nodes(g, 1, width/2, (height/2) + 1, height)
square4 <- select_square_nodes(g, (width/2) + 1, width, (height/2) + 1, height)

selected_nodes_list <- list(square1, square2, square3, square4)

plot_subgraph <- function(g, nodes, title) {
    subg <- induced_subgraph(g, nodes)
    
    plot(subg, 
         main = title,
         vertex.size = 10,
         vertex.label = V(subg)$name,
         vertex.label.cex = 0.6)  
}

par(mfrow = c(2, 2), mar = c(1, 1, 3, 1))

for (i in 1:length(selected_nodes_list)) {
    plot_subgraph(g, selected_nodes_list[[i]], paste("Subgraph", i))
}

This the problem I want to solve: I want to use parallel computing to find out the 4 nodes in the original network with the largest node sum. I thought I could use parallel computing so that the different cores of my computer can each be assigned one of these mini networks – and within each network, the 4 nodes with largest sum can be identified. From here, I can then pick the largest sum:

library(parallel)

find_largest_sum <- function(nodes, g) {
    subg <- induced_subgraph(g, nodes)
    sg <- subgraph_isomorphisms(make_ring(4), subg)
    lst <- unique(lapply(sg, (x) sort(names(x))))
    out <- do.call(
        rbind,
        lapply(
            lst,
            (v) data.frame(
                node_id = toString(v),
                value = sum(V(induced_subgraph(subg, v))$value)
            )
        )
    )
    return(out[which.max(out$value), ])
}

cl <- makeCluster(4)
clusterExport(cl, c("g", "find_largest_sum", "selected_nodes_list", "induced_subgraph", "make_ring", "subgraph_isomorphisms", "V"))
results <- parLapply(cl, selected_nodes_list, find_largest_sum, g)
stopCluster(cl)

print(results)

[[1]]
               node_id value
114 246, 247, 266, 267   352

[[2]]
              node_id value
13 324, 325, 344, 345   340

[[3]]
            node_id value
39 113, 114, 93, 94   369

[[4]]
               node_id value
118 571, 572, 591, 592   331

I thought everything was good – until I thought about the following problem! When splitting the network, won’t we lose information in the process? Certain squares (i.e. those on the boundaries) will never be considered for comparison:

Can someone please suggest a way to solve this problem?