How Does Graph Theory affect you, daily?

If you have not heard about something called "Graph Theory", I assure you that you can still read on. This post is about LinkedIn, Twitter & Facebook and not something to do only with geeky computer scientists. 


As expected, lets start with the basic - What is a graph? To answer that, don't go to Wiki, rather stare at this triangle. 
Well, this is a graph. 

A computer scientist would be proud to declare that its a graph having 3 nodes and its connected-undirected

And what was that? Simple, it consists of 3 vertices (O, H, M - you may call them nodes as well) and each connected to the other two. In real life, the 3 nodes can be your Office, Home and shopping Mall, where the lines are the roads. So for example, there exists a path between your Home & Office, Office & shopping Mall and shopping Mall to Home. So its a connected graph, where you can reach each of the places/nodes from any other place/node. BTW, the roads are assumed to be two-way, hence you can use the same road to move up and down between O, H & M.   That's why this is an undirected connected graph.


But in real life, do you often face a situation where you have one-way roads? If so, please look at the next image. You can imagine a situation where you have a direct road from Office to Home, but there is no such direct path Home to Office (I wish). Hence the arrow is marked as originating from O ending at H. However the path from Home to Mall is two-way. But the path from Mall to Office is one way. Now that its no more a both-way world, it becomes a directed graph. Lets see if we can reach anywhere starting from anywhere else. If you want to reach Mall from Office, you can, but you need to go via Home. If you want to reach Office from Home, you have to go through the Mall (not bad). So the places are still connected as such. Hence it might be a geeky way to call this a directed connected graph. 

But these were simple examples, aren't they? To make life interesting, lets introduce a not-so-simple example of a graph.
If you are confused, don't worry, this is called a colored graph :)   Jokes apart, I got this generated from LinkedIn based on my contacts. You can also generate this graph for yourself if you have a LinkedIn account and you click on this URL http://inmaps.linkedinlabs.com/.

But what is so revolutionary between this graph and the previous two? 

Well, the only differences are 1) here the nodes are persons, your contacts. 2) And if there is a line between two nodes, that means they are "Connections"

Are they directed? No they are not, as in LinkedIn, the relationship/path gets created only when the other person/node accepts your invitation. Is this connected? Well, this is, but note that this is only your connection graph, hence obviously they are showing the connected people (directly or via your connection or via your connection's connection etc). 

Now, that is trivial, ain't it? We understand that we are only a node in a giant graph (remember Shakespeare?) We also understand that there can be relationship/path between our friends/connections/followers. But how does it impact our social presence? Watch out, coming soon. 

We shall talk about Twitter as that gives an example of directed graph. And we shall also talk about Facebook.

Kolkata Bloggers