SNS网站都有一个功能，就是好友推荐(或者Follower推荐)。例如，在人人网上出现的“你可能认识的人”。怎么来实现呢，有一个很简单的办法。如果小刚和小明不是好友，但是他们有很多的共同好友。那么可以认为，A和B很可能相识。

　　怎样用Map/Reduce来做好友推荐

　　从图论的讲法上看，就是先列出一个人(记为小A)的所有朋友的朋友，在寻找小A和这些人之间有多少长度为2的通路。将这些通路数排序，寻找最高的那几个就可以了。

　　所以我们的Map/Reduce的任务就是：找出所有人的十个Top“推荐好友”。

　　社会化网络的图一般都很简单。我们假设输入是按name排序的。

　　"ricky" => ["jay", "peter", "phyllis"]

　　"peter" => ["dave", "jack", "ricky", "susan"]

　　我们使用两轮Map/Reduce任务来完成这个操作。

　　第一轮MR任务

　　这个任务的目的是计算每一对距离是2的人之间的通路数。

　　在Map函数中，我们先将每对朋友做一个笛卡尔乘积，说的不大清楚，举个例子，比如

　　"ricky" => ["jay", "john", "mitch"]

　　那么结果就是

　　["jay", "john"], ["jay", "mitch"], ["john", "mitch"]

　　他们都是通过ricky牵线搭桥认识的。将已经是朋友的组合筛选掉，再排好序。传给Reducer。

　　在Reduce函数中, 相同的组合必定会传给Reducer。所以Reducer只要数好有几个相同的组合传给他就行了.

　　Input record … person -> connection_list

　　e.g. "ricky" => ["jay", "john", "mitch", "peter"]

　　also the connection list is sorted by alphabetical order

　　def map(person, connection_list)

　　# Compute a cartesian product using nested loops

　　for each friend1 in connection_list

　　# Eliminate all 2-degree pairs if they already

　　# have a one-degree connection

　　emit([person, friend1, 0])

　　for each friend2 > friend1 in connection_list

　　emit([friend1, friend2, 1], 1)

　　def partition(key)

　　#use the first two elements of the key to choose a reducer

　　return super.partition([key[0], key[1]])

　　def reduce(person_pair, frequency_list)

　　# Check if this is a new pair

　　if @current_pair != [person_pair[0], person_pair[1]]

　　@current_pair = [person_pair[0], person_pair[1]]

　　# Skip all subsequent pairs if these two person

　　# already know each other

　　@skip = true if person_pair[2] == 0

　　if !skip

　　path_count = 0

　　for each count in frequency_list

　　path_count += count

　　emit(person_pair, path_count)

　　Output record … person_pair => path_count

　　e.g. ["jay", "john"] => 5

　　怎样用Map/Reduce来做好友推荐

　　第二轮MR任务

　　这一轮的MR任务是为了列出每个人距离为2的好友，查出他们直接究竟有几条路径。

　　在Map函数中，我们将每一组数据重新排列，保证一个人信息落在一个reducer上

　　在Reduce函数中，只要将每个人的可能好友之间的路径数排个序就可以了.

　　Input record = Output record of round 1

　　def map(person_pair, path_count)

　　emit([person_pair[0], path_count], person_pair[1])

　　def partition(key)

　　#use the first element of the key to choose a reducer

　　return super.partition(key[0])

　　def reduce(connection_count_pair, candidate_list)

　　# Check if this is a new person

　　if @current_person != connection_count_pair[0]

　　emit(@current_person, @top_ten)

　　@top_ten = []

　　@current_person = connection_count_pair[0]

　　#Pick the top ten candidates to connect with

　　if @top_ten.size < 10 　　for each candidate in candidate_list 　　@top_ten.append([candidate, connection_count_pair[1]]) 　　break if @pick_count > 10

　　Output record … person -> candidate_count_list

　　e.g. "ricky" => [["jay", 5], ["peter", 3] …]

　　Follower推荐

　　如果我想要做Follower推荐而不是好友推荐怎么办呢?

　　很简单。只要将第一步的MR任务改为求“Follow关系”和“Followed”关系的笛卡尔乘积就可以了。这里就不列伪码了。