Gossip is something that is really common between schools around the world. Students love to spread this type of information to their peers of the partial stories they know which ends up spreading to other groups of people like wildfire. To find out the true story, the students would need to tell each other the partial bits they know about it which would combine into the full story. This course comes in to play as we can use graph theory to determine how many conversions would need to take place in a group for every person to know the full story.
We can assume that everyone knows one part of the story and we want everyone to know the full story. Let people be vertices in a graph and the edges between them be the number of calls they make. To simplify this problem, we can assume that their will only be 2 ways calls (no group calls). In this blog post, I will answer the question of: How many calls must be made for n people to allow everyone to know the full story?
The numbers on the edges between the vertices represent the order in which the calls take place. This means the lowest number has the highest priority and so the paths taken will choose the highest priority edges first.
Consider the following graph:
There is a problem in this graph as B never hears D information. As you let information pass through D, D’s last call with A is also A’s last call and the same goes for C. Thus there is never a call to B telling D’s information.
We can try fixing this graph by defining the following.
“A gossip scheme is an ordered graph where there is an increasing path from any vertex to any other.” – Nate Gildersleeve
An example of this would be:
In this graph of 4 people, information can be passed around to anyone. We can see that C’s call to B happens after C’s call to D and thus B hears D’s information so the problem in the first graph has been solved here.
A method that can be used to find out how many calls it takes is that everyone calls one person in turn and then that same person calls everyone back. This would mean that the first person everyone called knows the whole story now and then he would be able to call everyone back to tell them the whole story.
For this approach, there would be
Let n be the number of people
=> n – 1 call’s going into that person [exclude the person being called]
=> n – 1 – 1 call’s going out [last call-in doesn’t need to be called again]
= (n – 1) + (n – 1 – 1)
= 2n – 3
For a group of 5 people this would look like:
We can actually improve this slightly by the following approach.
“If every person calls one of four people, then have those people share their information with each other and finally call everyone back”- Nate Gildersleeve
The following graph is more efficient than the one mentioned earlier.
This will improve our formula to 2n – 4.
In the world of gossip that we live in today, you now know how many conversions it will take to clear it up efficiently from the teachings of graph theory and deriving an undirected weighted graph for it.
References: