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