Is there a widely accepted alternative to Erdos-Renyi random graphs that addresses their issues with 1) degree distributions not having heavy enough tails and 2) clustering coefficients being too low?

My understanding is that Barabasi-Albert models for example don’t work as well as one would like for this purpose and that there have been a number of misleading results with them. What else is there? For example, do stochastic block models fix the clustering and degree distribution issues?

  • 2
    $\begingroup$ What is "heavy enough" tails, and what is "too low"? What is "this purpose"? $\endgroup$ – Henning Makholm Mar 31 at 13:12
  • $\begingroup$ In a sense, you're looking for alternatives to Barabasi–Albert. The Erdős–Rényi model is not a model for statisticians: it is primarily a tool for probabilistic combinatorics, in which setting we don't care about heavy tails and low clustering coefficients. $\endgroup$ – Misha Lavrov Mar 31 at 17:41
  • $\begingroup$ @Henning “Heavy enough” meaning able to handle complex networks with skewed degree distributions. ”This purpose” is producing a generative model for a network that might have a skewed degree distribution $\endgroup$ – JohnDoeVsJoeSchmoe Apr 1 at 0:45
  • $\begingroup$ @Misha Thank you for that distinction, I didn’t know that. Is there a type of network you’d suggest for statisticians looking for a generative model for a complex network that could have a skewed degree distribution? $\endgroup$ – JohnDoeVsJoeSchmoe Apr 1 at 0:47

See here for info on graphs with a "power-law degree distribution" (degree distributions not having heavy enough tails). Also this on the "preferential attachment model" (satisfies both the properties you are after).

  • $\begingroup$ Preferential attachment was already mentioned in the question, though of course you might disagree with the summary given. $\endgroup$ – Misha Lavrov Mar 31 at 17:39
  • $\begingroup$ @JRyan I’ve seen that Wikipedia page. Are all those models “generative”? $\endgroup$ – JohnDoeVsJoeSchmoe Apr 1 at 0:49
  • $\begingroup$ @JohnDoeVsJoeSchmoe the preferential attachment model is generative $\endgroup$ – JRyan Apr 1 at 19:53
  • $\begingroup$ I know that it generates the model in a procedural way, but would you describe the resulting model as generative? In the sense that it suggests a probability distribution that can be used to simulate data (edges)? $\endgroup$ – JohnDoeVsJoeSchmoe Apr 1 at 20:47
  • $\begingroup$ No, It is apparently a mechanistic model (see tuvalu.santafe.edu/~aaronc/courses/7000/…) $\endgroup$ – JRyan Apr 2 at 18:47

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.