以igraph投影双向网络时内存不足错误

Question

我有一个定向的二分图g，其顶点数为215473，边数为2326714。在创建g的bipartite.projection时，我一直用尽内存（它在崩溃之前使用〜35 g RAM）。

我试图通过遵循previous thread on nongnu.org来计算我需要多少内存。

从在此线程提供的信息，以存储在存储器成本的曲线图（以字节计）：

(4*|E|+2*|V|) * 8 + 4*|V| 

为了计算投影需要以下存储器（字节）：

16*|V| + (2*|V|+2*|E|) * 8 

因此，对于我的图表g，它的成本：

((4*2326714+2*215473) * 8 + 4*215473) + (16*215473 + (2*215473+2*2326714) * 8) 

= 78764308 + 44122560 
= 122886868 (bytes) 
= 122.886868 (mb) 

显然，这是不正确的，我一定在做错事。

任何人都可以请帮忙弄清楚如何创建我的图形的双向投影？

Answer 1

使用稀疏矩阵可能可以解决您的问题。

# Load tiny toy data as edgelist 
df <- data.frame(person = 
    c('Sam','Sam','Sam','Greg','Tom','Tom','Tom','Mary','Mary'), group = 
    c('a','b','c','a','b','c','d','b','d'), stringsAsFactors = F) 

# Transform data to a sparse matrix 
library(Matrix) 
A <- spMatrix(nrow=length(unique(df$person)), 
     ncol=length(unique(df$group)), 
     i = as.numeric(factor(df$person)), 
     j = as.numeric(factor(df$group)), 
     x = rep(1, length(as.numeric(df$person)))) 
row.names(A) <- levels(factor(df$person)) 
colnames(A) <- levels(factor(df$group)) 

于做你实际上可以多possiblities投影，这里有两个：

# Use base r 
Arow <- tcrossprod(A) 
# Alternatively, if you want to project on the other mode: 
Acol <- tcrossprod(t(A)) 

# Use the igraph package, which works with sparse matrices 
library(igraph) 
g <- graph.incidence(A) 

# The command bipartite.projection does both possible projections at once 
proj <- bipartite.projection(g) 

#proj[[1]] 
#proj[[2]] 

你也可以读入数据，并通过使用data.table做spMatrix命令中的转变，这将加快这些行动。

UPDATE：

这里是一个更大的图形和一些内存基准测试的例子：

# Load packages 
library(data.table) 
library(igraph) 

# Scientific collaboration dataset 
# Descriptives as reported on https://toreopsahl.com/datasets/#newman2001 
# mode 1 elements: 16726  
# mode 2 elements: 22016  
# two mode ties: 58595 
# one mode ties: 47594 
d <- fread("http://opsahl.co.uk/tnet/datasets/Newman-Cond_mat_95-99-two_mode.txt", 
      stringsAsFactors=TRUE, colClasses = "factor", header=FALSE) 

# Transform data to a sparse matrix 
A <- spMatrix(nrow=length(unique(d[, V1])), 
       ncol=length(unique(d[, V2])), 
       i = as.numeric(d[, V1]), 
       j = as.numeric(d[, V2]), 
       x = rep(1, length(as.numeric(d[, V1])))) 
row.names(A) <- levels(d[, V1]) 
colnames(A) <- levels(d[, V2]) 

#To do the projection you have acutally multiple possiblities, here are two: 

# Use base r 
Arow <- tcrossprod(A) 
# Alternatively, if you want to project on the other mode: 
Acol <- tcrossprod(t(A)) 

这里是一个概述多少内存是怎么使用的，即稀疏矩阵的方法上的工作我笔记本电脑，但使用常规矩阵的做法确实给予了内存分配错误（即使从内存中删除Bcol对象，然后调用垃圾收集器gc()）

object.size(A) # Spare matrix: 3108520 bytes 
object.size(Arow) # 2713768 bytes 
object.size(Acol) # 5542104 bytes 

# For comparison 
object.size(B <- as.matrix(A)) # Regular matrix: 2945783320 bytes 
object.size(Brow <- tcrossprod(B)) # 2239946368 bytes 
object.size(Bcol <- tcrossprod(t(B))) # Memory allocation error on my laptop