I have a network of 361 nodes and 695 edges. I want to prove that my network is statistically significantly different from a random network. Small-world connectivity is a key parameter that has been tested to prove whether a network is real or random. As per this question, I would like to generate multiple random networks and get an average across all the networks that I generate.

My question is: Should I use the same number of nodes and edges over all the random networks that I generate?

  • $\begingroup$ One of the parameters as I understand is to prove that my network is a small world network. – I fail to make sense of this sentence. Also note that proving that a network is a small world is inherently problematic as outlined in my answer to the linked question. $\endgroup$
    – Wrzlprmft
    Commented May 15, 2017 at 18:35
  • $\begingroup$ How do I generate, eg: 1000 networks (using erdos-renyi or watts-strogatz model etc) and get an average of the clustering coefficient or the diameter over all the random networks. – What exactly is your problem? You already describe very exactly what you need to do. $\endgroup$
    – Wrzlprmft
    Commented May 15, 2017 at 18:36
  • $\begingroup$ @Wrzlprmft Thank you for your input. As you put it, I do understand from your linked question as what to do. The problem is that I do not know how to do it. I was looking for some sample of code that may help me do this on igraph or a method to do this on any other network analysis software like cytoscape. $\endgroup$ Commented May 15, 2017 at 20:29
  • $\begingroup$ Please split this into two different questions (or remove the second question till you find out what you actually need to do). I can answer the first one, but I cannot say anything about the second one – which is a good indicator that a splitting is appropriate. $\endgroup$
    – Wrzlprmft
    Commented May 16, 2017 at 14:54
  • 1
    $\begingroup$ Small-world connectivity is a key parameter that has been tested to prove whether a network is real or random. – Not really. How would you do this? $\endgroup$
    – Wrzlprmft
    Commented May 16, 2017 at 19:52

1 Answer 1


In most cases it depends on what exactly you mean by random, i.e., which null hypothesis you want to test. This again depends on your application, network acquisition, and underlying question.

Two examples:

  • Suppose:

    • Your measurement process dictates a fixed set of nodes.
    • Two nodes are connected in your network whenever some measure specific to those two nodes exceeds some threshold.
    • You want to find out whether your measure is actually meaningful and not just yields random results – specifically with respect to the thresholding process.

    A reasonable null hypothesis in this situation would be that your measure returns independent numbers from some distribution. On the network level, this means that whether an edge exists or not is independent from the existence of other edges. The probability with which some edge exists depends only on the aforementioned distribution and the threshold. Hence the ensemble of networks that comply with this null hypothesis is the ensemble of Erdős–Rényi random networks having the same edge density and number of nodes.

  • Suppose:

    • Your network’s nodes are individual persons.
    • Edges represent friendship (measured in some reasonable manner).
    • You want to find out whether this network actually has some intricate structure like cliques or whether each person selects their friends at random.

    A reasonable null hypothesis in this case would be that your network’s structure is determined entirely by the degrees of its nodes, i.e., the number of friends each person has (reflecting their social activity). The corresponding random networks are more constrained than Erdős–Rényi random networks and methods of obtaining this ensemble are a little bit more complicted (see Maslov and Sneppen or Artzy-Randrup and Stone).

So, in these cases (as in many others) you should use the same numer of nodes and edges, but that’s not necessarily the only feature to preserve in your ensemble. What exactly makes sense depends on your application. It may even make sense to test several null models to detect some trivial influences on your measurements.

  • $\begingroup$ The basic idea is to compare the clustering co-efficient, the average path length and the average number of neighbors of my real world gene network with an ensemble of random networks. The network is undirected and unweighted. From your explanation, I guess I will use an ensemble of erdos renyi networks, keep the same number of nodes and network density while generating a set of random networks. I am not looking at any edge specific calculations at the moment. $\endgroup$ Commented May 17, 2017 at 17:03
  • $\begingroup$ As per your other question, your data does not contain triangles, so it is not well modeled by an ER model. $\endgroup$ Commented Jun 4, 2017 at 7:12

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.