# LightGraphs

**URL:** <https://discourse.julialang.org/t/lightgraphs/30850>\
**Category:** New to Julia\
**Created:** [November 8, 2019, 3:30am UTC](https://discourse.julialang.org/t/lightgraphs/30850 "2019-11-08T03:30:23Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![ennvvy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ennvvy/32/7816_2.png) [@ennvvy](https://discourse.julialang.org/u/ennvvy)\
**Post date:** [November 8, 2019, 3:30am UTC](https://discourse.julialang.org/t/lightgraphs/30850/1 "2019-11-08T03:30:23Z")

</div>

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:

```julia
@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?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 8, 2019, 6:31am UTC](https://discourse.julialang.org/t/lightgraphs/30850/2 "2019-11-08T06:31:03Z")

</div>

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

also remember to use `@btime`

---

<div class="post-metadata">

**Author:** ![ennvvy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ennvvy/32/7816_2.png) [@ennvvy](https://discourse.julialang.org/u/ennvvy)\
**Post date:** [November 8, 2019, 6:34am UTC](https://discourse.julialang.org/t/lightgraphs/30850/3 "2019-11-08T06:34:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 8, 2019, 6:39am UTC](https://discourse.julialang.org/t/lightgraphs/30850/4 "2019-11-08T06:39:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [November 8, 2019, 6:56am UTC](https://discourse.julialang.org/t/lightgraphs/30850/5 "2019-11-08T06:56:33Z")

</div>

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](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.

---

<div class="post-metadata">

**Author:** ![jtackm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jtackm/32/4784_2.png) [@jtackm](https://discourse.julialang.org/u/jtackm)\
**Post date:** [November 8, 2019, 7:42am UTC](https://discourse.julialang.org/t/lightgraphs/30850/6 "2019-11-08T07:42:42Z")

</div>

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

```

```python
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)

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [November 8, 2019, 12:21pm UTC](https://discourse.julialang.org/t/lightgraphs/30850/7 "2019-11-08T12:21:02Z")

</div>

> [@ennvvy](#):
>
> Is there anyway that I could make this faster?

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.