igraphで二部構成ネットワークを投影するとメモリ不足エラーが発生する

Question

私は、215473の頂点と2326714の辺を持つ、指示された二部グラフgを持っています。 bipartite.projectionをgで作成すると、メモリが不足しています（クラッシュする前に〜35ギガバイトの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

スパース行列を使用すると、問題が解決する可能性があります。ここで、あなたはacutally複数のpossiblitiesを持って投影を行うには

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

は2つです：

# 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オブジェクトを削除してからrm(Brow)でオブジェクトを削除してからガベージコレクタ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