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 commaseparated list of Users. The output will be in terms of [User][Tab][Recommendations], where [Recommendations] is a commaseparated 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 commaseparated 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
Pseudocode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

Hadoop MapReduce Program
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 
