Skip to content

Rework the Watts-Strogatz algorithm

Utopia Developers requested to merge patch_small_world_generator into master

What does this MR do?

This MR re-implements the Watts-Strogatz algorithm. We are currently using the Boost small-world generator, which has two problems: it can (and does) produce multi-edges, and it is not designed for directed graphs. This is not technically Boost's fault: they do not advertise the algorithm as the Watts-Strogatz algorithm from the 1998 paper, and they do explicitly say in the code that it assumes undirectedness of graph. However, since we are explicitly calling the network "Watts-Strogatz", it should comply exactly with their implementation imo.

The new algorithm should prevent parallel edges, and allow rewiring to "new" vertices also from the "backward" neighbourhood (so [v-k/2, v), as @jeremiastraub pointed out).

This MR also adds an orientated key to both regular and Watts-Strogatz algorithms, specifying whether the underlying lattice should be directed or not.

In order to efficiently deal with the case of complete graphs, a new complete network generator is included.

⚠ The original Watts-Strogatz algorithm requires the mean degree k to be even. Regular graphs with uneven degrees can hence no longer be generated.

Can this be accepted?

  • Implemented the Watts-Strogatz algorithm
  • Implemented the regular and complete generators
  • Adapted and expanded core tests:
    • Tests for the WS algorithm
    • Tests for the regular graph
    • Tests for the complete graph
  • Checked against parallel edges
  • Updated all relevant model configs
  • Checked that the WS-algorithm does indeed produce a small-world network, e.g. by analysing shortest paths
  • Updated the documentation for all three types (WS, regular, complete)
  • Reviewed and approved
  • Checked code coverage
  • Pipeline passing
  • History cleaned up (bc also adding a small plot improvement to Opinionet)

Closes #321 (closed)

Edited by Utopia Developers

Merge request reports