3
$\begingroup$

I have recently read

  • Watts, D., Strogatz, S., Collective dynamics of ‘small-world’ networks, Nature 393 (1998) pp. 440–442, doi:10.1038/30918,

on small-world networks, and is still not very clear to me how is the "small-world network regime" defined. Meaning that for a fixed value of vertices $N$ and a node degree $k$, what is the intermediate region of $0 < p < 1$ for which the Watts-Strogatz model is a small-world network?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

An increase of the "rewiring probability" $p$ (the probability that an edge is disconnected from one of its nodes and then randomly connected to another node) reduces both the mean path length $L$ and the clustering coeffcient $C$. There is a range of $p$ where the path length has been reduced substantially while the clustering coefficient is still close to the $p=0$ value. In that range of $p$ the network is called a small-world network.

There is no unique way to quantify that $p$-range. Wikipedia lists three different criteria.

The figure below shows how $L$ and $C$ decrease with increasing $p$. The shaded region would be the "small-world network" region, but obviously this is not a sharply bound region. [click on the figure to enter the applet and see how the network changes as you slide $p$]

Note: "path length" counts each edge as being of length 1, irrespective of the length of the bond.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Great to know about the Math Insight collection! $\endgroup$
    – Brian Hopkins
    Feb 13, 2021 at 13:56
  • $\begingroup$ Thanks Carlo, when I read the paper I was expecting to find a theoretical property related to the small world network regime. Such as in the ER models where probability theory and graph theory was used for identifying the appearance of certain properties that characterize such graphs. I guess this is not the case as the Clustering Coefficient and the characteristic path length are independent structural properties? I hope you understand what I'm trying to say. $\endgroup$
    – Sophie_s
    Feb 13, 2021 at 14:15
  • 1
    $\begingroup$ the characterization of a small-world network as being "highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs" is a qualitative one; this is different from a scale-free network, which has a power law distribution of nodes degree and therefore satisfies a quantitative criterion. $\endgroup$
    – Carlo Beenakker
    Feb 13, 2021 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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