# Friends You Might Know

This is a problem from CS246: Mining Massive Datasets from Stanford University. The idea behind the original “People You Might Know” friendship recommendation algorithm is that if two people share a high number of mutual friends, they are more likely to know each other and thus the system would recommend that they connect with each other.

## Problem Statement

The input here can be found here, which is in the form of [User][Tab][Friends]“, where [Friends] is a comma-separated list of Users. The output will be in terms of [User][Tab][Recommendations], where [Recommendations] is a comma-separated list of users that are recommended friend.

We could use a algorithm that for each user A, it recommends N = 10 users who are not already friends with A, but share the largest number of mutual friends in common with A.

## Approach and Pseudocode

The key is that for each user, the algorithm needs to find out the users who share mutual friends with him. Then, the algorithm needs to sort the users by the number of mutual friends in descending order and to make sure not to recommend the users who are already friends with A. Clearly, this is a highly parallelizable problem since for each user the computation is entirely separated. This would make a great MapReduce problem.

#### Terminology

For each user A:

Degree 1 friends: the users who A is already friends with
Degree 2 friends: the users who shares a mutual friend with A.
Degree 2 friends could potentially be degree 1 friends as well and we are interested in the users who are degree 2 friends with A, but not degree 1 friends.

#### Approach

Since we are using MapReduce, we want the reducer to have the key as A, and the value as an Iterable of degree 1 friends and degree 2 friends.

Example input: A B,C,D

Mapper:

• Computing degree 1 friends for A would be straightforward, as they would just be the users in the comma-separated friends list. The mapper would just emit the key values pairs of (A, B), (A, C) and (A, D)
• Computing degree 2 friends is a little trickier. Here we will use A as the key, but as the mutual friend. For example, from A’s friends list, we know B and C both have A as a mutual friend. Therefore B is a degree 2 friend of C and vice versa. The mapper would emit (B, C), (C, B), (B, D), (D, B), (C, D) and (D, C)

Reducer:

• The reducer receives the key, which is an user, and an Iterable of degree 1 and degree 2 friends of the key
• The reducer needs to count the number of times that a degree 2 friend pair shows up is the number of their mutual friends
• The reducer then needs to sort the degree two friends of the key by the number of mutual friends
• The reducer needs to make sure that degree 1 don’t get recommended