What is the most efficient way to define a very sparse network matrix in Julia?

Question

I have the data for a very large network which is quite sparse. I was wondering what would be the most memory efficient way to store and easiest to access whether two nodes are connected.

Obviously with N nodes, keeping an N*N matrix is not that efficient in terms of space I store. So I thought of maybe keeping the adjacency list like below:

Array(Vector{Int64}, N_tmp)

Where N_tmp <= N, as many nodes may not have any connections.

Could you help me whether there are better ways or maybe packages that are better in terms of memory and access?

Answer 1

In LightGraphs.jl, we use adjacency lists (basically, a vector of vectors) to store neighbors for each node. This provides very good memory utilization for large sparse graphs, allowing us to scale to hundreds of millions of nodes on commodity hardware, while providing fast access that beats the native sparse matrix data structure for most graph operations.

You might consider whether LightGraphs will meet your needs directly.

Edit with additional information: we store a sorted list of neighbors - this gives us a performance hit on edge creation, but makes it much faster to do subsequent lookups.