The Erdös-Rényi random graph II

A mathematical model of a network consists of elements and connections between them. We call the elements vertices, and the connections between them edges (in the demos and pictures, edges are drawn as lines). We call the combination of vertices and edges a graph.

In the Erdös-Rényi Random Graph, we fix a number of vertices. For each pair of vertices, we throw a coin to determine whether we create that edge or not. This is the simplest way to create a graph as all vertices and edges have the same statistical properties, and whether or not a given edge is present does not influence any other part of the graph.

The coin that tells us whether we keep an edge or not does not need to be fair, so that the probability to keep an edge does not have to be equal to a half. The probability that we keep an edge is a parameter of the model. The second parameter of the model is the total number of vertices of the graph. We denote the probability of an edge by p and the number of vertices by n.

When the probability of an edge p is very small, we will keep only few edges and the graph will be quite doscinnected. When, instead, we take p to be large, then we will keep many edges, so that we have one connected graph. This shows that the properties of the graph depend sensitively on the choice of the parameter p indicating the probability that we keep an edge.

Clearly, the graph begins to connect when increasing the probability of keeping an edge. An interesting question is how many edges we need to keep so that most of the vertices are connected by edge, directly or indirectly. We will again let you play around with the simulator, but to help you, we have introduced a third parameter for the input. This third parameter lambda is the product of the other two parameters, that is \lambda=np, which is a bit like the expected number of edges per vertex.

To use this demonstration on your full screen click here

Feel free to increase the number of vertices. We set it to 100 as we do not know the screen that you use to look at this demo. Investigate how we need to choose \lambda so that a big part of the graph is connected by the available edges, or equivalently how small it needs to be to break it apart.

If you want to know what we mean, then click here for the next piece.

Comments are closed