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:
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.
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.
Hello, I am also researching small worlds graphs, specifically the Watts-Strogatz model and was wondering if this function was ever adapted. Any update on this would be greatly appreciated.
