10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't know what is the purpose of your papar or your background. Do you have an actual graph you want to test? You could take basic descriptive measures of your graph, any graph library would do (e.g. networkx in python or igraph in R). Just check if your network is connected, what is the diameter, the average shortest path, etc. If you are generating the graph or your context is different, I would say more info is needed in order to answer to your question. $\endgroup$ – lrnzcig Oct 5 '15 at 14:02
  • 2
    $\begingroup$ To assess the presence of this logarithmic relationship, I think you'd need series of values. For instance, a sequence of snapshots of your graph evolving through time. Or a collection of different graphs corresponding to similar (comparable) systems (eg. the computer networks of several firms of various sizes). $\endgroup$ – Vincent Labatut Oct 6 '15 at 11:11
7
$\begingroup$

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:

  1. Calculate the mean shortest path length $L$ and the clustering coefficient $C$ of your network.

  2. Generate an appropriate ensemble of null-model networks, such as Erdős–Rényi random graphs, or Maslov–Sneppen random graphs.

  3. Calculate the average of the mean shortest path length $L_\text{r}$ over this ensemble of null-model networks; calculate $C_\text{r}$ analogously.

  4. Calculate the normalised shortest path $λ := L/L_\text{r}$. and $γ := C/C_\text{r}$.

  5. 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.

$\endgroup$
  • $\begingroup$ Could you have a look at the two questions that I have posted based on networks when you have time please. $\endgroup$ – The Last Word May 15 '17 at 16:26
  • $\begingroup$ Also, do you know of any paper where the methodology you have mentioned in this answer is listed. Creating an ensemble of networks, calculating its average etc $\endgroup$ – The Last Word May 15 '17 at 16:59
  • $\begingroup$ @TheLastWord: I already answered one of your questions, but for some reason you decided to ignore that. $\endgroup$ – Wrzlprmft May 15 '17 at 17:48
  • $\begingroup$ @TheLastWord: Also, do you know of any paper where the methodology you have mentioned in this answer is listed. – The paper by Bialonski et al summarises this approach and should contain relevant references. Also see this paper of mine. $\endgroup$ – Wrzlprmft May 15 '17 at 17:53
2
$\begingroup$

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."

$\endgroup$

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.