Degree of separation
We all are present on one or other social network like Facebook, LinkedIn, Google+ etc. On these there are friends of ours, then friends of friends and then friends of friends. Connections between people are represented as graphs where persons are nodes and if two persons are connected, then there will be an edge between them. Number of edges between two nodes is called as degree of separation.
What is degree of separation?
“Degrees of separation” is a concept that refers to how many people it takes to connect you and another person. Implementation wise, it is minimum number of edges between two persons. Simply understood, It’s the shortest path between two persons where each edge has weight of 1. Foe example, in above graph, degree of separation between Sarah and Alice is 2, as Sarah is connected to Ivana and Ivana in turn is connected to Alice.
Find degree of separation between two persons
First of all, we will store information of persons and their connections in graph. To find degree of separation between persons, breadth first traversal of graph is used.
Start from one person and check it’s all neighbors. If one of neighbor is second person, then degree of separation is 1. If not, increment degree by 1 and then look in neighbors of each neighbor in last step. This goes on till either we find second person or there is no node to be visited in graph (that means other person does not exist in our network ).
There is small optimization to above algorithm, that is to start breadth first traversal from both the nodes at same time. While traversing levels, check if neighbors of one person contains other person.
1. Given person1 = (A); person2 = (B); Init degree = 1 2. While there are nodes to be traversed 2.1 Find all neighbors of person 1 neighborsOfPerson1 = neighbors(person1) 2.2 If neighborsOfPerson1 contains person2 return degree 2.3 else increment degree 2.4 Find all neighbors of person2 = neighbors(person2) neighborsOfPerson2 = neighbors(person2) 2.5 If neighborsOfPerson2 contains person1 return degree 2.6 else increment degree
Simplistic implementation would be to use adjacency matrix to store neighbor information. To understand how a graph can be represented as adjacency matrix, please refer to post : Graphs basics However, adjacency matrix wastes lot of space, so it is good to represent information in graph built based on adjacency list.
In implementation, a sentinel is inserted every time a level is finished and new level has to be searched. At same time, we increment the degree too.
Complexity of this algorithm to find degree of separation between two persons is O(N) as we have to scan all nodes in words case. Also, there is space complexity involved of order O(N).
After from this Breadth first traversal, Dijkstra’s shortest path algorithm between two nodes can be used . Below is implementation using Dijkstra’s algorithm to determine degree of separation.
Please share if something is wrong or missing, we would love to hear from you.