r - 计算超大型网络的图效率指标

Question

在 R 中计算非常大图的节点和全局效率的策略是什么？

我正在尝试计算一个非常大的全局igraph效率brainGraph::efficiency(my_graph, type = "global")。

library(igraph); library(brainGraph)  
g <- readRDS("path_to_my_graph.rds")  

> ecount(g); vcount(g) # count of edges and vertices
[1] 715758
[1] 290190

它每次都可靠地使 R 崩溃。全局效率是所有节点效率的平均值，所以我试图以这种方式计算它，但没有成功。我的图表每条边的权重都是 1，所以我省略了权重，但 R 仍然崩溃。

# all of these cause R to crash
efficiency(g, type = "global")
efficiency(g, type = "nodal")
efficiency(g, type = "global", weights = NA)
efficiency(g, type = "nodal",  weights = NA)

我的图表 (~37MB) 可以在 GoogleDrive 上以 .rds 文件的形式提供给那些想要测试数据的人。

Answer 1

R 崩溃是因为brainGraph::efficiency()试图计算一个巨大而密集的距离矩阵，这压倒了我机器的内存 (32 GB)。但我找到了一个解决方案，可以将操作分块并并行运行。

全局效率是图中所有节点效率的平均值。顶点i的节点效率为：

我们可以顺序计算图中每个顶点的节点效率，这将距离矩阵计算拆分为更小的可管理位。因为每个顶点的效率是独立的，所以我们可以并行化操作，这样就不会永远持续下去。

library(igraph)  
library(doParallel)

# nodal efficiency function
get_eff <- function(i){return((1/(length(V(g)) - 1))*sum(1/distances(g, V(g)[i])[-i]))}

no_cores <- detectCores() - 1 
cl       <- makeCluster(no_cores)
registerDoParallel(cl)  

result <- foreach(i = seq_along(V(g)), .combine = c, .packages = "igraph") %dopar% get_eff(i)

stopCluster(cl)
rm(cl)

global_eff <- mean(result)

此外，我们可以绘制节点效率的分布，以及全局（平均）效率，这让我们可以更好地理解网络。

library(ggplot2)
data.frame(x = result) %>% 
  ggplot(aes(x)) + 
  geom_histogram() + 
  geom_vline(xintercept = mean(result), col = "red") # global efficiency
  theme_minimal() +
  labs(title = "Nodal efficiences", x = "", y = "Count")