A small-world network is a type of mathematical graph in which most
nodes are not neighbors of one another, but most nodes can be reached
from every other by a small number of hops or steps. Specifically, a
small-world network is defined to be a network where the typical
distance L between two randomly chosen nodes (the number of steps
required) grows proportionally to the logarithm of the number of nodes
N in the network, that is$$ L \approx \log(N) $$
This relationship between L and N is a "thumb-rule". I'm looking for a more professional determination of small-world graphs for my research. How can I test whether my graph is a small-world graph or not?
The small-world experiment comprised several experiments conducted by
Stanley Milgram and other researchers examining the average path
length for social networks of people in the United States. The
research was groundbreaking in that it suggested that human society is
a small-world-type network characterized by short path-lengths. The
experiments are often associated with the phrase "six degrees of
separation", although Milgram did not use this term himself.
Thank you in advance.
Best Answer
TL;DR:
You can’t.
What is typically done
The current “state of the art” in determining whether a network is a small world uses the following approach:
Calculate the mean shortest path length $L$ and the clustering coefficient $C$ of your network.
Generate an appropriate ensemble of null-model networks, such as Erdős–Rényi random graphs, or Maslov–Sneppen random graphs.
Calculate the average of the mean shortest path length $L_\text{r}$ over this ensemble of null-model networks; calculate $C_\text{r}$ analogously.
Calculate the normalised shortest path $λ := L/L_\text{r}$. and $γ := C/C_\text{r}$.
If $λ$ and $γ$ fulfil certain criteria (e.g., $λ≈1$ and $γ>1$), call the network a small-world network.
The idea behind this is that:
Small-world networks should have some spatial structure, which is reflected by a high clustering coefficient. By contrast, random networks have no such structure and a low clustering coefficient.
Small-world networks are efficient in communicating and similar and thus have a small shortest path length, comparable to that of random networks. By contrast, purely spatial networks have a high shortest path length.
Where the problems are
This does not say anything about how the mean shortest path scales with the network size. In fact, for real networks, the entire definition you quoted cannot be applied, as there is no such thing as the same network with a different number of nodes.
Suppose, we take some other definition of a small world that is not directly based on the values of $λ$ and $γ$, e.g.:
Then we still cannot make robust implications as to whether such a definition is fulfilled just using $λ$ and $γ$ (or in fact other network measures). The interpretation of many studies assumes that all networks are a realisation of the Watts–Strogatz model for some rewiring probability, which is not justified at all: We know many other network models, whose realisations are entirely different from the Watts–Strogatz model.
The above method is not robust to measurement errors. Small errors when establishing a network from measurements suffice to make, e.g., a lattice look like a small-world network, see e.g., Bialonski et al., Chaos (2010) and Papo et al., Front. Hum. Neurosci. (2016). In fact, I am not aware of a single study that claims that some empirical network is not a small-world network.
Sidenote: What would you gain?
I am not aware of any useful insight that can be derived from some network being a small world. The claim that some type of network is well described by a certain network model (e.g., the Watts–Strogatz model) may be useful for modelling studies, but that’s going much further than just claiming small-world-ness.
Full disclaimer: One of the above papers is from my direct academic vicinity.