Add 1 to all values of a large adjacency matrix

Question

I want to build a full graph out of an existing graph of a real network. The nodes have an attribute weight. The full graph should keep the same attributes of existing edges and set the weight of the new edges to 0.

This solution works for small graphs (on my 32gb RAM instance up to approximately 10K nodes) but with a graph with 80K+ nodes and 80M edges my script is killed by the OS at the line g[V(g), V(g)] <- TRUE.

I then need to know whether another solution is possible. In the code below I convert the graph to its adjacency matrix with get.adjacency(), add 1 to all values, convert it back to a full graph with graph.adjacency(), subtract 1 from all weights, and then pass all the nodes attributes from the original graph to the new full graph.

library(igraph)
g <- erdos.renyi.game(5, 1/5)
V(g)$size <- sample(1:10, vcount(g), replace=TRUE)
V(g)$time <- sample(1:10000, vcount(g), replace=TRUE)
E(g)$weight <- sample(1:10, ecount(g), replace=TRUE)

adj <- get.adjacency(g, attr="weight", sparse=TRUE)
adj <- adj + 1
g2 <- graph.adjacency(adj, mode="undirected", diag=FALSE, weighted=TRUE)
E(g2)$weight <- E(g2)$weight - 1

V(g2)$size <- V(g)$size 
V(g2)$time <- V(g)$time

g.full <- graph.full(5)
vcount(g.full) == vcount(g2)
# [1] TRUE
V(g2)$size == V(g)$size
# [1] TRUE TRUE TRUE TRUE TRUE
V(g2)$time == V(g)$time
# [1] TRUE TRUE TRUE TRUE TRUE

The trick works, but only on small graph. The bottle neck is at adj <- adj + 1 which for a large graph gives

Error in asMethod(object) : 
  Cholmod error 'problem too large' at file ../Core/cholmod_dense.c, line ...

Answer 1

This error does not have much to do with igraph. After get.adjacency you have a sparse graph and

adj <- adj + 1

essentially converts it to a dense matrix. To have a dense matrix with 80,000 rows/columns you need 80,000 * 80,000 * 8 bytes of memory, which is about 48GB. Actually, even if you have that much memory, most probably it will not work, because R will want to copy the matrix at least once, so you need twice of this.

And then if you want to create an igraph graph from it, you'll need much more memory than this ~100GB, because igraph was designed for sparse graphs, and it is not very efficient with memory if the graph is dense. It needs (2*n+4*m)*8 bytes of memory, where n is the number of vertices and m is the number of edges. You will need another m*8 bytes of memory for the weights, and n*4 bytes for the other (integer) attributes, per attribute.

So I would suggest to use some graph analysis software that stores the data on the disk, or consider another data representation, e.g. not storing the edges that have zero weight.