What does the rewiring probability for a small-world network indicate?

Question

A large rewiring probability for a small-world network means the network has more randomness. Does this mean anything deeper, and can it be determined for a real (i.e., empirical) network?

Answer 1

The Watts–Strogatz model is, well, a model. It allows you to investigate how order and randomness affect phenomena happening on the network in simulation.

For example, Watts and Strogatz (and many others) investigated how the rewiring probability affects synchronisation phenomena of oscillators coupled as per the respective network. This happens in simulation studies, where you first construct an artificial network, instead of starting with a real one. The strength of the WS model is that it allows you to tune the randomness (via the rewiring probability) while leaving the other properties of the network mostly unchanged.

Of course any insights gained by such a study are limited to the WS model and you might find other network where the effect of randomness is inverted. Thus one needs to take care before generalising claims and study other network models or understand the mechanisms underlying the observed effect.

More generally, the WS model only describes a narrow subspace of all networks¹. For example, Barabási–Albert networks are not included and there is no reason to expect that any real network is perfectly described as a WS network¹.

The rewiring probability describes a technical aspect of the algorithm that generates a model. Therefore it cannot be deduced from a real network just like that. Real networks do not form via rewiring and you usually cannot observe their formation. A reasonable for the rewiring probability is the number of long-ranged connections and you might approximate the latter if the underlying geometry of a network is clear and you can separate short-range and long-range connections. For example, you might consider a social network and define every edge between people living more than 100 km apart a long-range connection. But that already makes the bold assumption that your network lies in the Watts–Strogatz subspace¹.

What some people did (and probably still do) instead is to deduce a “randomness” from the normalised clustering coefficient ($C$) and mean shortest path length ($L$) of a network. A lower $C$ and $L$ are considered to indicate a more random network. This is similar to looking at the so-called small-world-ness of a network and has similar problems. Most importantly, the mean shortest path has severe robustness problems.

But even if you can somehow overcome those, it is still based on the assumption that you are in the narrow WS subspace of networks¹. In the very likely case that you are not, a network may just have a lower $C$ and $L$ because it is objectively more random but because due to differences unrelated to randomness. For a blatant example, a perfect chequerboard lattice with a few added long range connections can have a small $L$ and $C=0$ (since no long-range connections) and thus would be considered very random by this approach. Yet it is certainly not what any reasonable person would call random. I therefore consider it not possible to deduce a “randomness” via clustering coefficient and mean shortest path length from empirical networks.

---

¹ Strictly speaking, the Watts–Strogatz model includes every network since a completely random network can be every network with equal probability. For example, a completely random network might turn out to be a perfect chequerboard lattice (which is not included in the usual WS model) as likely as any given objectively random network. However, a random network is much more likely to be objectively random than resembling a lattice in any way. So, to be precise: When I say something that a network is not included by the WS model, I mean that the WS model is very unlikely to produce a network with similar properties.