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

Question

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

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

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) here on GoogleDrive as an .rds file 可供想要数据测试的人使用。

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")

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

Computing graph efficiency metrics of a very large network

r

igraph

network-efficiency

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