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

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

5 голосов
/ 10 марта 2012

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

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

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

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

1 Ответ

6 голосов
/ 11 марта 2012

Если вам нужны только распределения степеней, вам, скорее всего, не нужен пакет графиков.Я рекомендую 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).

...