LightGraphs

New to Julia
1

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:

@btime watts_strogatz(10000,2500,0.0,is_directed=true)
  1.841 s (220005 allocations: 634.00 MiB)
{10000, 12500000} directed simple Int64 graph

Is there anyway that I could make this faster?

2

do you a comparison? e.g python matlab speed?

also remember to use @btime

3

I have now updated my original post with btime results. I dont have a comparison with either MATLAB or Python for now.

4

since you’re just directly calling 1 function, I doubt there’s way to “improve” it in-place.

5

I would tend to agree with this - basically you’d have to ] dev LightGraphs and try to speed up the function in the package.

LightGraphs is a pretty well maintained package with lots of contributions from seasoned Julia programmers, so I’d be surprised if there were any more hanging performance fruits in there.
That said, looking at the function on github (here https://github.com/JuliaGraphs/LightGraphs.jl/blob/9af50fd95c2c6e42ceb31e4be7c120f70f271450/src/SimpleGraphs/generators/randgraphs.jl#L242) I can see that there’s a TODO comment referencing a specific potential performance improvement, so you could have a go at this.

6

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)
4 Likes
7

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.

1 Like