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


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.


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.


@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)