I am trying to generate a regular-directed graph and eventually a small-world network using watts_strogatz function in the Light Graphs’ package. For a network with 10,000 nodes, the time taken is as below:

For what its worth, I had a quick look at networkx and igraph in python (see below). networkx doesn’t finish after minutes and igraph takes ~2.5x the time of LightGraphs on my system.

(Note that networkx seems to not support directed graphs (but speed is similar for directed vs. undirected in LightGraphs) and igraph uses a different formulation, there I chose parameters that result in comparable graph size)

Code:

julia> using LightGraphs, BenchmarkTools
julia> @benchmark watts_strogatz(10000,2500,0.0,is_directed=true)
BenchmarkTools.Trial:
memory estimate: 634.00 MiB
allocs estimate: 220005
--------------
minimum time: 2.391 s (7.35% GC)
median time: 2.533 s (11.40% GC)
mean time: 2.533 s (11.40% GC)
maximum time: 2.676 s (15.03% GC)
--------------
samples: 2
evals/sample: 1

In [1]: import networkx as nx
In [2]: %timeit nx.watts_strogatz_graph(10000, 2500,0.0)
< ... doesnt finish ... >
In [3]: import igraph as ig
In [4]: %timeit ig.Graph.Watts_Strogatz(2, 100, 35, 0.0)
6.24 s ± 45.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Are you sure it’s possible to make it faster? That’s the first question to always ask. The timings above suggests… maybe not.

My guess is that this graph generation might be able to be parallelized, which sounds like an excellent beginner project. Take the ]dev LightGraphs, jump into the file, look at its structure, and try to multithread it. My guess is that since there’s very large subcomponents, it may be able to generate them separately, but that’s just a guess.