Author |
Topic: Shortest path between two face book connections (Read 5297 times) |
|
ravikumarv
Newbie
Gender: 
Posts: 5
|
 |
Shortest path between two face book connections
« on: Nov 27th, 2011, 9:17pm » |
 Quote  Modify
|
How do you find a shortest connection between two persons on Facebook(if the same exists)?
You are provided with an API which returns the list of friends of a particular persons.
Graph traversing algorithms(BFS, DFS) may fits the bill.
Any better solution.?
|
| « Last Edit: Nov 27th, 2011, 9:22pm by ravikumarv » |
 IP Logged |
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: Shortest path between two face book connection
« Reply #1 on: Dec 4th, 2011, 1:02pm » |
Quote Modify
|
Dijkstra's algorithm will solve your problem
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Shortest path between two face book connection
« Reply #2 on: Dec 7th, 2011, 11:28am » |
Quote Modify
|
Doing a BFS may not be a good idea, in terms of memory efficiency. If everyone has about 200 friends, the BFS queue will blow up in terms of memory consumption quite quickly.
So, you probably need to stick with DFS (with a lexically ordered search, so as to avoid maintaining visited node matrix, you can just maintain just one single array that tells you the last node you visited at each depth). However, facebook graph is huge!!! Just one deep search can take ages?! Can we use some of the results obtained in this paper [1]? The largest distance they seem to have observed is 7. So a dumb approach would be to simply do DFS upto depth 7. Even though you are saving in memory by doing DFS, you will be going through a lot of nodes, your loop may take a really long time to end.
So, a single machine algorithm 'maybe' out of hand for this problem (note that this is purely due to scale of the graph and not because you did not have an efficient algorithm). What if you use a distributed framework like Map Reduce (Hadoop) ? Well, in that case, rather than DFS, BFS might be a better choice, because it is much easily parallelizable. This is generally what happens at the end. Just do a parallel BFS on such large graphs to compute shortest distances [3].
There is one more avenue. In the world of AI, there is something called as A*-search [2]. However, using this algorithm requires defining something called as "admissible function". There is no natural way of doing that for facebook like graph. In fact, defining and proving an admissible function for facebook graph might itself be a research paper.
-- AI
[1] http://arxiv.org/abs/1111.4570
[2] http://en.wikipedia.org/wiki/A*_search_algorithm
[3] http://blog.udanax.org/2009/02/breadth-first-search-mapreduce.html
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shortest path between two face book connection
« Reply #3 on: Dec 7th, 2011, 11:45am » |
Quote Modify
|
Most people on facebook are connected through an average of 4 connections or less. So a BFS from both ends could be easily done in those cases.
Besides, there are only 7 billion people in the world, so BFS has a maximum width of 7 billion at worst (and there aren't actually that many people on facebook).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Shortest path between two face book connection
« Reply #4 on: Dec 8th, 2011, 6:05am » |
Quote Modify
|
DFS is a bad idea for a graph that is not a tree. You would keep reaching the same nodes from different paths.
I'd say if you want to save memory, you should do something like a BFS starting simultaneously from the 2 ends:
Given 2 people (a and b), start with sets
A0={a}, B0={b}
Then compute the circle of fiends by distance
Ai+1 = friends(Ai) that are not in Ai or Ai-1
Bj+1 = friends(Bj) that are not in Bj or Bj-1
Compute the Ai and Bj for increasing values of i and j, incrementing i or j (one at a time), always incrementing the side that has a smaller set so far.
Stop when Ai and Bj intersect.
When computing the Ai and Bj, remember for each person you add who is his friend in the previous circle. When an intersection is found, you can reconstruct the chain of friends linking him to both a and b. That should be a shortest path.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Shortest path between two face book connection
« Reply #5 on: Dec 9th, 2011, 2:46am » |
Quote Modify
|
on Dec 7th, 2011, 11:45am, towr wrote:| and there aren't actually that many people on facebook. |
|
They have about 770 million people. Just an FYI.
Yeah, I didn't think of dual BFS. Even if it were done for depth 7, we would be maintaining about ~16million entries in memory which given a good RAM is possible.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print