Posts Tagged ‘degree of separation’
How do social networking sites calculate if you are within a certain degree of separation efficiently?
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).
Posted in Myspace | 
Tags: bugging, degree, degree of separation, friendster, Myspace, networking, page, separation, social networking sites, something, three degrees, user, while | 
2 Comments »
