在这个问题中（网络中的节点求和），我学习了如何在原始网络中找到具有最大节点和的平方。
这是这个问题的数据：
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")
这是函数：
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)
)
)
)
此方法目前使用的是暴力式方法，其中每个节点都被单独检查。 R 中有什么方法可以重构这个函数，使其并行运行，或者使用不同类型的搜索算法来更有效地扫描网络？
我对此有两个想法：
想法1：
重写函数以查看方形网格并通过网络对它们进行细分：
efficient_sum_squares <- function(g, width, height) {
results <- data.frame(node_id = character(), value = numeric())
for (i in 1:(width - 1)) {
for (j in 1:(height - 1)) {
nodes <- c(
get_node_index(i, j),
get_node_index(i + 1, j),
get_node_index(i, j + 1),
get_node_index(i + 1, j + 1)
)
sum_value <- sum(V(g)$value[nodes])
results <- rbind(results, data.frame(node_id = toString(nodes), value = sum_value))
}
}
results
}
out_efficient <- efficient_sum_squares(g, width, height)
想法2：
我认为可以以矢量化的方式进行比较：
vectorized_sum_squares <- function(g, width, height) {
x_mat <- matrix(V(g)$x, nrow = height, ncol = width, byrow = FALSE)
y_mat <- matrix(V(g)$y, nrow = height, ncol = width, byrow = FALSE)
value_mat <- matrix(V(g)$value, nrow = height, ncol = width, byrow = FALSE)
sums <- value_mat[1:(height-1), 1:(width-1)] +
value_mat[2:height, 1:(width-1)] +
value_mat[1:(height-1), 2:width] +
value_mat[2:height, 2:width]
node_ids <- apply(which(sums == sums, arr.ind = TRUE), 1, function(idx) {
i <- idx[1]
j <- idx[2]
toString(c(
get_node_index(j, i),
get_node_index(j + 1, i),
get_node_index(j, i + 1),
get_node_index(j + 1, i + 1)
))
})
data.frame(node_id = node_ids, value = as.vector(sums))
}
out_vectorized <- vectorized_sum_squares(g, width, height)
有没有更好的方法来解决这个问题？
如果您在网格中搜索这样的正方形（由
4igraphigraph这是一个类似于第二种方法的示例
set.seed(0)
width <- 15
height <- 10
gmat <- matrix(sample.int(10, width * height, replace = TRUE), height)
ul <- gmat[-height, -width]
ur <- gmat[-height, -1]
dl <- gmat[-1, -width]
dr <- gmat[-1, -1]
ssum <- ul + ur + dl + dr
idx <- apply(
which(ssum == max(ssum), TRUE),
1,
\(x) {
toString(crossprod(
c(height, 1),
x + cbind(
c(-1, 0),
c(-1, 1),
c(0, 0),
c(0, 1)
)
))
}
)
res <- data.frame(node_id = idx, value = max(ssum))
你看到了
> gmat
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
[1,] 2 3 1 2 3 3 2 1 1 3 1 2 3
[2,] 1 3 3 2 2 3 1 1 1 2 2 1 1
[3,] 3 1 1 1 1 2 3 1 1 2 2 3 1
[4,] 1 1 1 3 3 2 3 1 1 2 1 3 2
[5,] 2 1 1 1 2 2 2 3 3 3 3 1 2
[6,] 1 2 1 3 1 2 3 2 2 2 3 2 2
[7,] 3 2 2 2 1 1 3 3 1 2 2 1 1
[8,] 3 2 1 2 3 2 2 1 1 3 3 3 1
[9,] 2 2 1 2 2 2 3 1 3 3 2 2 1
[10,] 2 3 2 2 2 2 3 2 3 3 1 3 2
[,14] [,15]
[1,] 1 2
[2,] 3 2
[3,] 2 1
[4,] 3 2
[5,] 3 3
[6,] 2 3
[7,] 3 3
[8,] 3 3
[9,] 1 3
[10,] 1 1
和
> res
node_id value
1 89, 90, 99, 100 12
2 74, 75, 84, 85 12