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.
Playing around with different values of n and p, we can observe that cycles and giant components begin to form.
For example, for a ER network with 50 nodes p = 0.2 is the threshold for giant component and cycle formation.
At p=0.8 we have the threshold for connection.
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.
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”).
Now let’s play with random networks!
References: “Social and economic networks”, Mattew O. Jackson, Princeton; Wikipedia, https://en.wikipedia.org/wiki/Network_formation
