How to test statistically whether my network (graph) is a "small-world" network or not? 
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.
 A: A Small-Worldness Index can be computed in "R" using the function smallworldness in the package qgraph.
This is based on:
Humphries, M. D., & Gurney, K. (2008). Network "small-world-ness": a quantitative method for determining canonical network equivalence. PLoS One, 3(4), e0002051
From the paper: 

"A network is now deemed a ‘small-world’ if S>1 - an assertion which
  may be tested statistically."

A: 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.:

A small-world network is a spatial network with added long-range connections.

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.
