how friend suggestions or 2nd degree related (linkedin) algorithm works

Question

I've been thinking about facebook suggestions and other similar system of linkedin.

I think Facebook suggestion also based personal knowledges, like school years, the companys i worked or something similar.

But beyond that to be more specific here is the scheme

Case1 looks simple, but when the friend count goes bigger (event about 300 friend too much) it's not efficient. How about Case2? What kind of algorithm can do this work.

I've no idea about Case3 because i guess its something special fo facebook. but how could i detect person 4. is which degree related?

Answer 1

I'm not sure if you're asking how to make suggestions or detect friend distance. Making suggestions is easy, but will tend to explode in size.

The first two cases can be covered by the same algorithm, and the third by a small extension.

The first two are basically looking for all the people who your known friends mutually know:

FriendHash = {}
foreach Friend in me.getFriends()
    foreach FriendOfFriend in Friend.getFriends()
        FriendHash{FriendOfFriend} += 1

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        me.suggestFriend(PotentialFriend)

In case 1, the link between friends 1 and 2 could be an additional constraint that would actually make the case a bit more complex to implement. By requiring friends 1 and 2 to have a link, you'd need to detect potential friends while iterating friend pairs, rather than once at the end.

foreach Friend in me.getFriends()
    foreach SecondFriend in me.getFriends()
        # skip already processed friends and Friend == SecondFriend
        if Friend.getFriends() contains SecondFriend
            foreach FriendOfFriend in Friend.getFriends()
                # skip already suggested friends
                if SecondFriend.getFriends() contains FriendOfFriend
                    me.suggestFriend(PotentialFriend)

There's certainly some optimization that can be added in there that would skip repeated comparisons. In practice this probably isn't a useful search to run anyway. All you're going to do is exclude potential friends who are common to two distinct groups of friends.

The last case modifies the first pseudo code segment by extending a friend suggestion to all the friends of your known friends mutual friends:

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        foreach ExtendedFriend in PotentialFriend.getFriends()
            me.suggestFriend(ExtendedFriend)

As commented by Neil Knight, you could filter each friend list and start by looking at the most active friends first. Or compute a similarity score that promotes those friends who have more friends in common with you.

If you're actually looking at detecting the distance between a friend and a suggestion, this probably isn't relevant.