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

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

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

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

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


r igraph social-graph
person Giannis H.    schedule 10.03.2012    source источник
comment
Когда вы говорите «анализировать», можете ли вы уточнить, что вы пытаетесь сделать?   -  person ose    schedule 10.03.2012
comment
Конечно. Я хочу рассчитать градусы (вход, выход, общее количество), которые я буду использовать для построения графиков распределения. Я хочу иметь возможность перемещать узлы и ребра из большого графа в меньшие графы (процессы выборки), где очень удобны add.vertices и add.edges из igraph.   -  person Giannis H.    schedule 10.03.2012
comment
Каков формат данных? Один только крайний список весит 60 Гб? (т. е. это текстовый файл, в котором каждая строка содержит два числа, представляющие отправителя и получателя одного ребра?)   -  person Christopher DuBois    schedule 11.03.2012
comment
Да, это текстовый файл списка краев, и каждая строка содержит два идентификатора, представляющих направленное ребро от 1-го идентификатора до 2-го идентификатора.   -  person Giannis H.    schedule 11.03.2012

Ответы (1)


arrow_upward
6
arrow_downward

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

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

person Christopher DuBois    schedule 11.03.2012
comment
Итак, если я правильно понял, мы переносим задачу на вычисление матриц. Мне нравится это. Приведите пример. - person Giannis H.; 11.03.2012
comment
Кажется простым и масштабируемым для вычисления степени. Может ли он справиться с манипуляциями с графиками? Добавление вычитания и т.д.? Я должен прочитать их документацию. Спасибо за публикацию Кристофер. - person Giannis H.; 12.03.2012