10

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 facebook suggestion 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?

1
  • 4
    Here's the hidden truth behind Facebook. The algorithm looks at, what they call, the top 5 percent. So, this takes into consideration things like: how active a user is to your page, things you like, things you don't like, music likes/dislikes etc. It will never go out to all of your friends. So, if you post to your wall, the thought is that it goes to everyone. But this isn't the case, it will go to the top 5 percent that are related to the post. Apr 20, 2011 at 9:59

2 Answers 2

6

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.

1
  • well actually, i am asking both questions you specified. but for an imaginary users table. it means that is also includes table structure. at least i have some clues but hard to decide because of performance issue. is it like, users and friendship table or something else. and thanks for your answer
    – siniradam
    Apr 21, 2011 at 11:13
2

Facebook probably takes info from your profile, messages and uses connections count etc. The distance could be one of the factors which is again put into a weighted matrix like calculation. Then summed up and top suggestions are selected using a threshold for this sum. Info on common likes, direct comments etc are dumped from the servers to a log possibly. Then this log is analysed every week or so to suggest friends using Hadoop MapReduce. This result per person can be fed to a webservice which presents the info to the users when they login.

A simple friend suggestion using MapReduce

A modified friend suggestion using Mahout and MapReduce

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.