Вычислительные графики эффективности метрик очень большой сети - PullRequest
Новая
       24

Вычислительные графики эффективности метрик очень большой сети

0 голосов
/ 19 апреля 2019

Каковы стратегии для вычисления узловой и глобальной эффективности очень больших графов в 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)

Мой график (~ 37 МБ) доступен здесь здесь, в GoogleDrive в виде файла .rds для тех, кто хочет проверить данные.

1 Ответ

0 голосов
/ 20 апреля 2019

R дает сбой, потому что brainGraph::efficiency() пытается вычислить матрицу огромных и плотных расстояний, которая переполняет память моей машины (32 ГБ). Но я нашел решение, которое разбивает операцию на части и работает параллельно.

Глобальная эффективность - это среднее значение всех узловых эффективностей на графике. Узловая эффективность вершины i равна:

enter image description here

Мы можем последовательно рассчитать узловую эффективность для каждой вершины графа, которая разбивает вычисление матрицы расстояний на меньшие управляемые биты. Поскольку эффективность каждой вершины независима, мы можем распараллелить операцию, чтобы она не длилась вечно. 

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

enter image description here

...