Challenge,How to Implement an Algorithm for Six Degree of Separation

Challenge,how to implement an algorithm for six degree of separation?

Represent this list of users by a graph

• Each user is a node
• There is an edge between any two users who know each other

1. Calculate the path from UserX to UserY
2. For UserX,calculate all users that is no more than 3 steps away.

These questions are so closely related that the same algorithm actually solves both of them. You can call it "Dijkstra's algorithm with all edges having weight 1," or "breadth-first search."

Essentially, starting at the first node, visit all its relatives; then mark them all as visited, record the shortest path to each (the shortest path to them + the edge you just traversed), and repeat for each of them. Stop after you've reached your destination for Problem #1, stop after the shortest path is > 3 for Problem #2.

This will run in O(n) time. No, there is no faster way.

The fastest O(n) algorithm for six-degrees of separation would probably be finding the sets of all users 1-step away from UserX and UserY, and finding the intersection of those two sets. If none, then add the users 2-steps from UserX and intersect; then add users 2-steps from UserY and intersect; etc. up to 3.

If each person has an average of 100 friends, this could require looking at up to about 2,020,200 users, as opposed to the 1,010 billion for Dijkstra's algorithm. In practice, these numbers would be much smaller, since often two of your friends are also friends with each other.

This is the only method of solving six-degrees of separation (of those mentioned so far) that will work in practice.

Six degree of separation with Ken Thompson

Not Depth First, but Breadth-First Search (BFS) is perhaps the most effective method to determine "inner circle" of some person.

If you want to reveal at most six levels of separation for two known persons, you also can try bi-directional BFS

Question about "who has relation" to Ken Thompson is quite philosophical... You need to define conditions yourself - perhaps you can reveal pupils in the same school, students and instructors in the same university, relatives, colleagues, all the UNIX users and C programmists ;), ... perhaps no.

Six degree of separation interview problem

What's wrong with BFS?

Execute three steps of BFS from the first node, marking accessible users by flag 1. It requires 10^9 steps.

Execute three steps of BFS from the second node, marking accessible users by flag 2. If we meet mark 1 - bingo.

How can I prove the Six Degrees of Separation concept programmatically?

You just want to measure the diameter of the graph.
This is exactly the metric to find out the seperation between the most-distantly-connected nodes in a graph.

Lots of algorithms on Google, Boost graph too.

What's the algorithm to assign people their most preferred value based on a list of their top choices?

This is the Assignment problem. You could use, for instance, the Hungarian Algorithm.

You just need to come up with a way to turn the user/player preferences into costs. Perhaps when a person gets their first choice, the cost is -3, second choice is -2, third choice is -1, etc. How you do that depends on the nature of your problem. How you view the various trade offs ends up encoded in the costs you give the algorithm.

---

Related Topics