Checking if a graph is random using the Erdős-Rényi model?

Question

Given some graph, I would like to determine how likely it was to be randomly created. I was told that comparing with the Erdős-Rényi model was a good way to get this information, but I cannot figure out how to do it.

Any tips?

Answer 1

The simplest way would probably be to compare the expected number of links with what you observed in this graph. A somewhat more sensible method would be to study the distribution of the degree. Erdős-Rényi graphs will have binomial distributions, while real-world networks are usually a power law.

It may also be easier to test if you had an idea about what other types of models were used to generate the chart.

Answer 2

You can see the ERGM package for R (www.r-project.org) at www.statnet.org. Although you may not be able to say with 100% certainty that your observed network is created by a random process, you will be able to assess the likelihood that it was produced using random or non-random partner selection processes. ERGM has a gof function that matches the goodness of fit, and compares your observed network with simulated random networks and analyzes network statistics such as geodetic distance distribution, distributed distributed distribution distribution, degree distribution and triad census distribution. This will allow you to make an informed decision about whether you think your network is random or not.

Answer 3

You cannot tell if a single graph is generated randomly. If the generation algorithm is random, you need to check the random distribution of the edges. But you will need many instances generated by this algorithm. It is better to check the concept of randomness in mathematics, cryptography and information theory. [or maybe you want to start with rfc 1750 ]

The Erd-Rey model basically says that you take the number n of nodes, and all possible edges have a probability p of existence of a [G (n, p) -model]. Thus, through p you can generate the expected number of edges and the deviation from this expectation. If a significant ratio of the graphs is within the standard deviation of this expectation, well, you may not say that your algorithm is random at all, but you have at least one public function, the expected number of edges.

But then again, not having a large number of states (graphs, intermediate steps of an intermediate graph or similar), you will be lost there. Let's say I give you the number: 4. Is it randomly produced or not?