共计 2552 个字符，预计需要花费 7 分钟才能阅读完成。
这篇文章主要讲解了“如何用 Map/Reduce 来做好友推荐”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“如何用 Map/Reduce 来做好友推荐”吧！
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”关系的笛卡尔乘积就可以了。这里就不列伪码了。
感谢各位的阅读，以上就是“如何用 Map/Reduce 来做好友推荐”的内容了，经过本文的学习后，相信大家对如何用 Map/Reduce 来做好友推荐这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！
