Graph Theory, Matrices – A Realtime example

Observe the matrix given below 

Adjacent Matrix
Adjacent Matrix


The above Matrix shows all zero at diagonal. 

Let me draw a graph for this ,

Directed Graph
Directed Graph


Assume that A, B and C are entities in database , Say Person entity.

A – Ram , B – Suma, C – Prema

Ram – Posted 
 Hello ….
Suma – Commented
  Idiot 🙂 …
Ram – Replied
  You Idiot …
Prema – commented
  See every one call you as idiot 🙂
Directed Graph
Directed Graph
Hold a moment … Does the above graph is correct ?
Observe what is changed in below graph
Un-Directed Graph
Un-Directed Graph


It is not mandatory that only A has to comment B ! , Even B can comment A .

So the first graph shown  is a directed graph and it is wrong , It should be undirected graph.

Now assume that how a facebook keeps track of connected friends ? Mutual Friends ? how big is the graph of facebook ?

The intention of this article is , to teach you guys how a Matrix concept is used to represent a graph, and how a graph theory is used in realtime to represent a social networking site like facebook.

Now understand why one should learn Graph Theory and Matrices

Let us have a look into facebook DB and Big data
Total Monthly Active users – 1,310,000,000
Total Mobile users  – 680,000,000
Every 20 minutes on Facebook
Links shared –  1 million
Friend Requests – 2 million
Messages sent – 3 million

Leave a Reply

Your email address will not be published. Required fields are marked *

The reCAPTCHA verification period has expired. Please reload the page.