Season 1 Weekly

Being more Popular, Mathematically!

Saul Goodman said, “Let’s just say I know a guy, who knows a guy, who knows another guy”. Had this guy known another guy like the initial guy Saul knew chances are that at the sixth iteration he could have been referring to pretty much anyone in the world!

Such is the concept of six degrees of separation which states that you are 6 handshakes away from anyone else in the world with the assumption that handshakes can take place only in between the people who each other. With 7.8 billion people, for this to be the reality every human will only have to know 45 other human beings.

And that’s a safe number as research suggests the number of people a human can have a stable relationship with is somewhere between 100 and 250 with the often-quoted number being 150, the Dunbar’s number. If that was the reality, the degrees of separation would soon drop to 4.5! And that’s not even the end, the modern social landscape is dominated by social networking websites such as Linkedin, Facebook and Twitter. Considering every connection, friend and mutual follower to be a relation, that number easily drops to 3.5 in case of Facebook. The consequences of this number are outrageous. A hyperconnected world means viral news and media can spread like wildfire with just 3.5 stops between any two individuals.

To investigate further into the workings of a network, we need a way to visualize the same. You can think of some space and then for every individual draw a point and for every connection between any two, think of a line joining the two dots. Now, what is the least number of lines you need to join every point? Since one line joins two points, N points will require (N-1) lines. However, this resultant network won’t be very well connected.

Arranging all these points in a circle, if you wished to reach a diametrically opposite point, you would have to trod over every intervening point. From now onwards you may wish to follow along with a pencil and a piece of paper. For a world with 3 dots, the average degree of separation is 1. Nice, that means everyone knows each other! With 4 dots, the average jumps up to 1.33 and 1.5 with a pentagonal network. Any guesses what the average path length will be for a hexagonal network? 1.8 it is (in Yoda’s voice).

Scaling this up to bigger networks maybe with 40 or 50 nodes, we start to approach a simulation of a locality. Continuing the exercise above, you’ll find that the average path length grows quickly as more nodes get added. In real life, this would mean had we been closely related only to our neighbours, human networks would have been very exclusive.

But in a network with 50 nodes, if you introduce just two connections connecting two diametrically opposite nodes, the pah length drops dramatically. This result is pretty significant in the real world. It explains how just six handshakes or even lesser (on average) can connect any two human beings. Most of the humans have most of their connections originating from their locality or niche of the profession. Only some of our connections live abroad probably in a different profession. These ‘weak ties’ bring us closer to a whole new country of connections.

In mathematics, Paul Erdős had some contributions in this field of graph theory and networking. This lead to the popular convention of Erdős Numbers. If you had co-authored a paper with Erdős, you get an Erdős number of 1. If you co-authored with a guy who co-authored with Erdős, you would have 2. And in case you were wondering, Erdős had Erdős number 0! (P.S. That’s not a factorial.)

To summarize and therefore justify the title, to make the most of your connections, you should always try to make friends/acquaintances among people from different geographic locations and professions. This would bring you exponentially closer to distant networks.

Now that we have talked about a strategy to be mathematically popular and have done justice to the title of the post, we can dive a little deeper into types of graphs and possible applications in the world.

With the raging pandemic, the importance of networks has become particularly important. If you consider every human to be a node then every transmission can be represented as an edge (a connection). Employing the same concept discussed above, most humans will transmit the disease to people near them. But once in a while, some legend would travel abroad aboard an aeroplane infecting everyone on the way and then everyone at the destination! Just one connection would be the reason for the introduction of the pathogen in a different network.

Now you can see why quarantining is important and why banning air travel becomes one of the first measures to curb the spread of disease. Any measure to stop a connection between two distant networks yields benefits. One distinctive feature between the network of human connections and infections is that the latter is directed.

There are some interesting ways to visualize directed graphs. If we assume that someone infected once either recovers or loses their life, the graph becomes an acyclic directed graph. This way the patient zero becomes the root node and everyone else a node in the branching directed acyclic graph (DAGs). Surprisingly a similar structure is used in a cryptocurrency called Iota. Iota uses DAGs to point to newer blocks of transactions and solves many of the problems of resource-intensiveness of Bitcoin.

Representing graphs can be done using adjacency matrices. If it is cyclical, every node can map onto itself or some other node. Imagine a matrix with all the row headers populated by FROM-nodes and column headers by TO-nodes. This provides an easy way to introduce principles of linear algebra while dealing with such directed graphs. Its use can be seen in natural language processors as such matricial representations are essential for stochastic models like Markov Chains.

A different type of graph called binary trees is also popular which diverge from a root node and has only two branches from every node. Its uses are plenty with Huffman coding being an interesting one in the field of lossless data compression. In the human body, the motor system demonstrates an interesting divergent tree whereas the vascular system acts a directed cyclic graph.

Finally, there’s our brain. We applaud the ability to make connections between different fields of study as often it gives rise to novel solutions to problems. Thanks to associative senses we can experience senses from different organs all converging to paint a unifying picture in our subjective space. To achieve such levels of intelligence, neurons in our brain has to be particularly interconnected to ensure maximum integration within a limited volume. No doubt nature had figured out the best way to manipulate networks way before we did and today we can see the evidence in every duct system in the plant and the animal world.

From epidemiology to sociology and neuroscience to cryptocurrencies, graph theory plays a vital role. What’s fascinating is how useful a dot and a line can be we carefully study the vast multitude of ways in which they can be combined to form graphs and trees.

Arkadeep Mukhopadhyay