For a small world property, the ratio of the average path length and the mean path length of random networks has to be close to one. My question is: When generating a random graph using the Erdős-Rényi algorithm, there is a chance that some nodes are not connected. Should I consider such graphs when calculating the mean shortest path length and clustering, or should I discard them and generate a new one?


You use Erdős–Rényi networks as instances of a null model for your real data. Thus the answer to your question depends on what null model is appropriate to your situation. Are disconnected networks something you would expect? If no, also discard them from your null model as well. If yes, also consider how would you would evaluate the mean path length of disconnected networks (which should be ∞).

Also note that for large network sizes, Erdős–Rényi networks are:

  • almost certainly unconnected if your average degree is below a certain critical value;
  • are almost certainly connected if your average degree is above a certain critical value.

This means that if your original network is connected, so should be the corresponding Erdős–Rényi networks – unless your original network is special (in which case your null model is probably not appropriate anyway) or small (in which case your analysis is even more questionable than due to the reasons outlined below).

Finally note that it is questionable whether measuring the small-world-ness of empirical networks like this (or at all) is possible and useful. For details, see: How to test statistically whether my network (graph) is a "small-world" network or not?


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.