1
$\begingroup$

In order to develop some intuition for some of the commonly used random graph models, I've been looking at the global clustering coefficient as a means of comparing them. In particular, for the general ER-Bernoulli disturbed random graph, the Watts-Strogatz random graph, and the Barabasi-Albert random graph, their global clustering distributions are as follows respectively:

  • For a Bernoulli graph distribution for 1000 vertices with edge probability $p$ enter image description here

  • A 1000 vertex random graph made according to Watts-Strogatz model with probability $p$ enter image description here

  • 1000 vertex random graph made according to Barabasi-Albert model, where vertex deg on x-axis shows the fixed degree of each added node (until 1000 nodes is reached). enter image description here

In contrast to the ER and Watts-Strogatz models, the Barabasi-Albert random graph has a power-law distributed degree distribution.

Question:

  • Could we have expected these trends in the global clustering of these models? Namely, the linear increase in the 1st one, the rapid decaying one in the 2nd and the log(?) scaling one in the last one. On the one hand, the ER-Bernoulli one is understandable since the higher the probability the more edges are added but in an independent fashion.

  • But on the other hand, the Watts-Strogatz model AFAIK is one that was designed such that it leads to high clustering, but why do we see a decrease in the global clustering unlike the other two models?

With the help of choosing clustering as a factor of comparison, I'm basically trying to learn how one reasons between these 3 models.

$\endgroup$
2
$\begingroup$

The meaning of the probability parameter (denoted by $\beta$) in the Watts--Strogatz model at the link you provided is very different from the meaning of the probability parameter $p$ in the Erdős–Rényi model. Indeed, $p$ is the probability that an edge is included into the random graph, and hence greater values of $p$ result in greater clustering. On the other hand, $\beta$ is the probability that one of the end-nodes of each edge in the initial regular ring lattice, a graph with $N$ nodes each connected to $K$ neighbors, is replaced by an almost completely arbitrary node, thus destroying the comparatively high clustering of the initial regular ring lattice. This explains the decrease of clustering in $\beta$.

$\endgroup$
  • $\begingroup$ Thanks! Very good point, this indeed explains the different trend (in terms of clustering) between the two. I guess in other words, by increasing $\beta$ we're approaching towards the random graph (Bernoulli distributed edges) model, where we know the clustering vanishes for high large node numbers. In this comparison, does it make a difference if we talk about local as opposed to global clustering? (my plots show the global one). $\endgroup$ – user929304 Jul 31 at 14:38
  • $\begingroup$ Since this reasoning is qualitative and seems to make sense, I think it should pertain to any reasonable definition of clustering. However, it would be interesting to see the corresponding graphs for, say, the average local clustering coefficient. $\endgroup$ – Iosif Pinelis Jul 31 at 15:00
  • $\begingroup$ Okay, I will try to calculate them and add to post. $\endgroup$ – user929304 Jul 31 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.