I have a network with a 361 nodes and 695 edges. My 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 4 parameters are said to be valid

1) Degree distribution plot

real network has a power law distribution for nodes rather than a bell curve

2) Real network would have a single giant component with average degree > 1

3) Clustering co-efficient (transitivity) for Random networks are very close to zero.

and I am unsure about this but,

4) Diameter of a real graph is large and random networks have small diameters (Small world connectivity)

Could you please clarify if these four points are correct?

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 (which is much larger than 1)

However, the clustering co-efficient of my network is zero, moreover, all nodes have clustering co-efficient values very close to zero or zero.

Does this mean that my network is not real?

Does it have to satisfy all four parameter?

Thank you in advance


closed as unclear what you're asking by SmallChess, Michael Chernick, mdewey, gung, mpiktas May 16 '17 at 13:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Do you have something particular in mind when you write "random network"? There are different ways of randomly generating a network, the simplest model is probably Erdős–Rényi en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model $\endgroup$ – einar May 15 '17 at 14:34
  • $\begingroup$ @ basically, I would like to know if these 4 parameters are sufficient to distinguish between a real and random network and what is the best method to do so $\endgroup$ – The Last Word May 15 '17 at 14:35
  • 2
    $\begingroup$ Cross-posted from here. Please refrain from cross-posting questions unless you are sure that you need input from two communities. In particular do not ignore the feedback, edits, and answers you already received, but state, e.g., why they do not satisfy you. $\endgroup$ – Wrzlprmft May 15 '17 at 17:47

First, I think you have point four backwards, large real-world networks such as social networks typically have a small diameter.

Second, it is possible to generate a synthetic network with the properties you describe, see for instance Kroenecker graphs. From the conclusion to that paper:

The resulting graphs (a) have all the static properties (heavy-tailed degree distribution, small diameter, etc.), (b) all the temporal properties (densification, shrinking diameter) that are found in real networks.

That being said, if you define "random" as a simple Erdős–Rényi type model, you can probably use all of your four criteria as evidence for/against a graph fitting this model. But if you want proof it'd be better to look at something outside the bare network structure.


Not the answer you're looking for? Browse other questions tagged or ask your own question.