Random Graphs

What are random graphs?

A random graph is a graph that is created by a random process that has associated probability distributions. This means that we have a probability associated with the creation of the edges of this graph.

Because is a probability, the edges that are going to be created are not deterministic. Therefore, if we generate a random graph twice, we can’t guarantee that we will have the same graph on both executions.

Random graphs are useful because they define models in which we can study how graphs behave.

Researchers, when looking at a new complex network, will generate several metrics about those networks and then compare those values to values found on random graphs. This gives the researcher an idea of how random some aspects of the network are and which characteristics seem to come from an organized system.

The Erdős–Rényi model

The main random graph model is the Erdős–Rényi model. This model considers that every graph with the same number of nodes and the same number of edges has the same probability of existence.

From this statement, we can already see why a random graph can’t be a good representation of reality. It is simple to think of two graphs with the same set of edges and nodes that aren’t equally probable to happen.

The construction for this graph requires that we define two quantities: the number of nodes we want in the graph and a fixed probability of a given edge existing in the graph.

The model will create every edge in the graph independently of the others and with a defined probability. If we set that probability to 40%, for example, we’re saying that for every ten possible edges, we’re going to create four.

The NetworkX library has a function to create the Erdős–Rényi graph.