Анализ социальных графов. 60 ГБ и 100 миллионов узлов

Question

Добрый вечер,

Я пытаюсь проанализировать вышеупомянутые данные (крайний список или формат pajek). Первой мыслью был R-проект с пакетом igraph. Но ограничения памяти (6 ГБ) не помогут. Сможет ли ПК с 128 ГБ обрабатывать данные? Есть ли альтернативы, которые не требуют целый граф в оперативной памяти?

Заранее спасибо.

PS: Я нашел несколько программ, но я хотел бы услышать некоторые профессиональные (да, это вы) мнения по этому вопросу.

Answer 1

Если вам нужны только распределения степеней, вам, вероятно, вообще не нужен пакет графиков. Я рекомендую пакет Bigtablulate так, чтобы

1. ваши объекты R защищены от копирования, поэтому вы не ограничены оперативной памятью
2. Вы можете распараллелить вычисление степени, используя foreach

Проверьте их веб-сайт для более подробной информации. Чтобы дать быстрый пример этого подхода, давайте сначала создадим пример с краевым списком, включающим 1 миллион ребер среди 1 миллиона узлов.

set.seed(1)
N <- 1e6
M <- 1e6
edgelist <- cbind(sample(1:N,M,replace=TRUE),
                  sample(1:N,M,replace=TRUE))
colnames(edgelist) <- c("sender","receiver")
write.table(edgelist,file="edgelist-small.csv",sep=",",
            row.names=FALSE,col.names=FALSE)

Затем я объединяю этот файл 10 раз, чтобы сделать пример немного больше.

system("
for i in $(seq 1 10) 
do 
  cat edgelist-small.csv >> edgelist.csv 
done")

Далее мы загружаем bigtabulate упакуйте и прочитайте в текстовом файле с нашим крайним списком. Команда read.big.matrix() создает объект с файловой поддержкой в ​​R.

library(bigtabulate)
x <- read.big.matrix("edgelist.csv", header = FALSE, 
                     type = "integer",sep = ",", 
                     backingfile = "edgelist.bin", 
                     descriptor = "edgelist.desc")
nrow(x)  # 1e7 as expected

Мы можем вычислить конечные степени, используя bigtable() в первом столбце.

outdegree <- bigtable(x,1)
head(outdegree)

Быстрая проверка работоспособности, чтобы убедиться, что таблица работает должным образом:

# Check table worked as expected for first "node"
j <- as.numeric(names(outdegree[1]))  # get name of first node
all.equal(as.numeric(outdegree[1]),   # outdegree's answer
          sum(x[,1]==j))              # manual outdegree count

Чтобы получить степень, просто сделай bigtable(x,2),