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

In Erdős–Rényi model a link is formed with a fixed probability p. As p gets higher, chances to form more connections arise too.

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

Watts-Strogatz model begins with a lattice of n nodes and rewires some link with probability p to abtain a network with average degree k. As the rewiring happen, diameter decreases and the network conserve its high clustering and those are exactly small world properties.

In Watts-Strogatz model rewires diminish the network diameter

Barabasi-Albert, a preferential attachment model

Barabasi-Albert model generates scale-free (power-law) network and those are similar to many artificial and natural real life networks (the Internet, citation networks…) where we have a small number of nodes with high degree (hubs) and many node with low degree. Here p depends on destination node degree (“richer gets richer”).

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