I have something that's been bugging me for a while now. On sites like MySpace and Friendster if you are on someones page it will tell you if they are within three degrees of them or whatever.How can this be caklculated efficiantly as each user could have 100s of friends? Anyone got any ideas.
How do social networking sites calculate if you are within a certain degree of separation efficiently?
You can view the structure of these friends relationships as a graph - each person is a node, and there is an edge between two nodes if those two people are friends. Therefore, this problem is reduced to finding all nodes that are of distance three or less from the given node. Dijkstra's algorithm (link below) is a clever algorithm that can be used to solve this in not too much time.
Reply:i'm not sure
No comments:
Post a Comment