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. Opinions are my own.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

NLP Analysis of Large Text Datasets Conducted by Dr. Leonard Apeltsin

Say What the GPS is Telling You

Dataman Learning Paths— Build Your Skills, Drive Your Career

An Intuitive Explanation of Kernels in Support Vector Machine (SVM)

Word Embedded Topic Modeling Recommendation Engine

Top 100 Open Datasets people are looking for.

5 Machine Learning Projects on Social Media Analysis

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Juna Salviati

Juna Salviati

Full-time Human-computer interpreter. Opinions are my own.

More from Medium

PY to JS [ 0 ] : Print  , Variable types and declaration ,

What’s a time-series database management system and why a TSDB?

Analyze and Optimize Webpack Bundles Size and Contents

Knuth-Morris-Pratt Pattern Matching Algorithm