A gentle introduction to Random Networks

Note: all the images in this article are generated using SimpleNets,a self-developed library (playground included!). 🙌

I will add no formulae to this article, because if I’d put formulae in, it would cease to be gentle. 💔

Sources on Github!

A random graph is a network where nodes are all set but edges are wired with some probability. There are many random graph models to produce graph with various probability distributions and in this article we are going to explore some of those models.

But…why random graphs are important?

Random graphs are important as a benchmark for real networks and because studying those models we can discover some interesting graph properties.

Erdős–Rényi model

An ER graph with p=0.3

Playing around with different values of n and p, we can observe that cycles and giant components begin to form.

ER graph with no giant component

For example, for a ER network with 50 nodes p = 0.2 is the threshold for giant component and cycle formation.

ER graph with a giant component

At p=0.8 we have the threshold for connection.

ER graph with a single giant component

Watts-Strogatz model, a small world model

In Watts-Strogatz model rewires diminish the network diameter

Barabasi-Albert, a preferential attachment model

In Barabasi-Albert model the richer get richer

Now let’s play with random networks!

References: “Social and economic networks”, Mattew O. Jackson, Princeton; Wikipedia, https://en.wikipedia.org/wiki/Network_formation

Full-time Human-computer interpreter