Take the 2-minute tour ×
Webmasters Stack Exchange is a question and answer site for pro webmasters. It's 100% free, no registration required.

Linkedin is great for its feature of people degrees, up to three levels.

Is there anyone who know how such feature has been built and how to keep it scalable with millions of people? (tech docs and algorithms types are welcome)

Thank you

share|improve this question

migrated from stackoverflow.com Jun 12 '11 at 19:34

This question came from our site for professional and enthusiast programmers.

closed as not a real question by Nick, John Conde Aug 13 '11 at 17:30

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

add comment

3 Answers 3

Every tim a person makes a new 1st degree connection, each person's 2nd degree connections are unioned with the first degree connections of the other. The third degree connections are similarly unioned with the other person's second degree connections. This is the best way using OO techniques. As far as scalability, they are possibly using cubes in the database using similar techniques.

share|improve this answer
add comment

OFF: I believe this should belong back to stackoverflow since it involves some programming and graph logic.

Since I know that LinkedIn uses Hadoop, I might think, that they are using some kind of graph exploration with MapReduce.

I blog'd about the algorithm in general here: http://codingwiththomas.blogspot.com/2011/04/graph-exploration-with-hadoop-mapreduce.html

Basically you treat your people like vertices in a graph, then you have to group them into components. While doing this (with the algorithm I described in my blog) you have to cap the number of recursions to the number of degrees you want the relation to have. Then you have for each people (or vertex) a connected component of n-other vertices that could be displayed in your frontend.

share|improve this answer
add comment

@Ethan: so there will be a table will all the connections, like: user_id, connected_user_id, depth_degree which will have all the connected nodes... eg.

user A has: user B and user C as first degree
user B has: user A, user D and user E as first degree
user C has: user A as first degree
user D has: user B and user F as first degree

in the table there will be:

user A, user B, 1
user A, user C, 1
User A, user D, 2
user A, user E, 2
user A, user F, 3
user B, user A, 1
user B, user D, 1
user B, user E, 1
user B, user F, 2
user C, user A, 1
user D, user B, 1
user D, user F, 1
....

right? wouldn't be this a lot of records in order to keep all the connections of the graph? imagine just one million of users, with like 200 first degrees the result table will have billions of records

@Thomas: I'll surely read your post and look more into hadoop, thanks

Do you think that it would work on a nosql database (mongodb/couchdb)?

Thank you both :)

(btw i think too that stackoverflow is a better place for this topic)

share|improve this answer
add comment