Is my network not random?

Question

I have a network with a 361 nodes and 695 edges. My primary objective is to prove that my network is real and not a random connection of nodes like in the case of a random network. So, I did some research and four parameters are said to be:

1. The degree distribution – real network have a power law distribution for nodes rather than a bell curve

2. Real networks would have a single giant component with average degree $\langle k \rangle > 1$.

3. The clustering coefficient (transitivity) for random networks is very close to zero.

4. The diameter of a real graph is large, while random networks have small diameters (small-world connectivity). (I am unsure about this one.)

My network satisfies the first two parameters, i.e, it has a power-law distribution for the degrees and the average degree is $3.85 ≫ 1$. However, the clustering coefficient of my network is zero. Moreover, all nodes have clustering coefficients very close to zero or zero.

My questions are:

• Are the four above points correct?

• Do my findings mean that my network is not real?

• Does my network have to satisfy all four parameters?

Answer 1

The first thing you have to realise is that there is not a single type of non-random network. For example, consider applying your criteria to the following types of model networks (all of which are claimed to reflect some real networks):

1. 2D lattices in which every node is connected to its four nearest neighbours,

2. 2D lattices in which every node is connected to its eight nearest neighbours,

3. networks generated with the Barabási–Albert algorithm (scale-free),

4. networks generated with the Watts–Strogatz algorithm (small world).

Type 1 has a zero clustering coefficient; type 2 has a high clustering coefficient. Types 4 will have normally distributed degrees; the others won’t. Types 3 and 4 will have small diameters; types 1 and 2 won’t.

So, to cut a long story short:

• There is no list of specific properties of a non-random network.

• If you find any property which significantly¹ differs from an appropriate ensemble of random networks², this indicates that your network is not totally random.

  What is an appropriately ensemble, depends on your application and what kind of randomness you want to reject. For example, if you suspect that your measurements establishing the links are uncorrelated and random, Erdős–Rényi networks are an appropriate example.

Be aware though that such a finding does not necessarily have to be caused by whatever you are investigating having such properties but could also be caused by the measurement process. For example, if your measurement process causes some spurious duplicate nodes, this can quickly lead to a clustering coefficient that is significantly different from that of a random network. Also take a look at this question on Cross Validated.

---

^{¹ taking into account multiple testing
² with the same number of nodes and the same edge density}