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.
Gstoll2003 suggested using Dijkstra but like I said each user could have 100s of friends. How could this be made to be efficient? A graph would have to be constructed every time this was needed to be known. If it each link were a tupul in a database this would be computationally huge. If you were to check three degrees and each user had only 10 friends there would already be in the thousands of queries (or perhaps one huge recursive query).
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.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Report this comment
i’m not sure
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Report this comment