Minimum degree in a sample_smallworld() graph

Usage
1

Recently, I have been exploring random graph models in igraph. In particular, I am interested in small-world networks. While working with the sample_smallworld() function in igraph, I noticed some behavior that seems inconsistent with my understanding of the Watts & Strogatz model.

Specifically, in their paper they mention We choose a vertex and the edge that connects it to its nearest neighbour in a clockwise sense. With probability p, we reconnect this edge to a vertex chosen uniformly at random over the entire ring…. Based on this, I would expect the minimum degree after reconnecting to be half of the average degree. However, when testing this using sample_smallworld() in igraph with a high rewiring probability p, the minimum degree does not match the expected value. For example:

table(degree(sample_smallworld(1, 100000, 2, 0.8)))

To further clarify the expected behavior, I also tested the Watts-Strogatz model using NetworkX, which does give the expected minimum degree.

I was hoping you could provide some insight into why there is this discrepancy between the Watts-Strogatz model description, the NetworkX implementation, and the implementation in sample_smallworld(). Is this difference intentional or could it be a bug? Any guidance would be greatly appreciated.

2

Let’s put the full description here form the original paper:

image
image1270×1106 106 KB

I believe you are right and there’s a difference from igraph’s implementation.

igraph will rewire both endpoints of each edge. The original formulation rewires only one endpoint, using the one-dimensional ring as a reference for the direction.

We’ll look into clarifying this in the documentation.

You can think of sample_smallworld as a convenience function that just uses make_lattice then applies rewire. When the rewiring probability is p=1 we get a G(n,m) random graph with the same number of vertices and edges as the original lattice. Thus with igraph’s function the minimum degree is zero.

3

I clarified the docs and opened a feature request to implement the accurate version of the model. Wishlist: Watts-Strogatz model that follows the original publication strictly · Issue #2383 · igraph/igraph · GitHub

Thanks for pointing out this issue.