Erdős–Rényi vs Watts–Strogatz bipartite graphs

Question

While looking to compare the number of three-node motifs in real and random networks, I did a literature survey and found that most researchers have used the Erdős–Rényi model to create random networks to compare against. I did the same and used the sample-bipartite function (it using the Erdős–Rényi algorithm) in R (iGraph package) to create random networks and obtain the number of three-node motifs in these random networks.

Recently, I was asked why I used the Erdős–Rényi instead of maybe the Watts–Strogatz model. I did a literature survey and I couldn't find a suitable answer for the same. Could someone please explain why the Erdős–Rényi model is preferred over the Watts–Strogatz in the creation of random bipartite networks?

Answer 1

If a certain motif is abundant or rare in a network this implies that there is some mechanism or similar that favours or prevents this motif – which in turn may be a relevant insight to your application. I assume that you have made such a finding and want to exclude that the number of instances of a certain motif can be explained by chance.

A typical approach to do this is to consider the case that the nodes are given and the same number of edges as in your real network is placed randomly on the graph (i.e., edges are placed between random nodes). In this case there is no mechanism that favours or prevents your motif by construction. Thus the number of motifs for such a graph can act a baseline for your real network: If the number is higher it is abundant; if it is lower, it is rare; if it is the same (within statistical fluctuation), it’s neither. With other word, this random network is (an instance of) your null model.

Now, for a simple graph, the random network described above is an Erdős–Rényi graph. For bipartite graphs, things are a bit more complicated since you usually want to ensure that both node types have the same frequency as in your original network. Depending on your applications, other kinds of constraints (like fixing the degrees of nodes) may make sense – here it really matters what kind of information you consider given and not the subject of your network enquiries. Anyway, the general idea is that you fix some properties of your original network, randomise everything else, and if it does not significantly affect the number of your motif, you have to conclude that your finding can be explained by chance.

The Watts–Strogatz algorithm on the other hand was not made to create random networks to begin with. It was to simulate small-world networks (inspired by sociology), or more general, networks that are embedded on some geometry and have primarily short-ranged, but also some long-ranged connections according to this geometry. Watts–Strogatz networks are not intended or suited as a null model, since they are constructed to have structure. For example due to the geometrical basis, you would expect triangles (a.k.a. three-node motifs) to be abundant. I cannot imagine a realistic situation where the Watts–Strogatz model is an appropriate choice of null model.

Finally, the Watts–Strogatz model doesn’t naturally translate to bipartite graphs and I am not aware of any attempt to do this. In fact this question is already the first finding for an Internet search for Watts Strogatz bipartite.

Answer 2

There is a good reason to use the Erdős–Rényi model (in pretty much any random graph context) when you will be proving a property of that model: it is the simplest model to actually prove things about.

(So, whatever a "three-node motif" is, you are probably not doing the best work you can merely by estimating the number of them by sampling random Erdős–Rényi graphs and counting; you can almost certainly find the asymptotic distribution of the number of three-node motifs exactly.)

Also, since the Erdős–Rényi model is the simplest to define, results about it are by default more interesting than results about other models: the simpler a result is to explain, the more interesting it is. This stops being true once you have a specific reason to use another model. The point is that you don't need a specific reason to use Erdős–Rényi: it is the default.

In the case where you are collecting experimental data about random graph models, there is not a good reason to restrict yourself to the Erdős–Rényi model, and you might as well collect the data about as many different models as you can sample from.