How to generate random networks for comparison with my network? 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?
 A: 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.
