如何使用Map/Reduce推荐好友

SNS网站都有一个功能，就是好友推荐（或者关注者推荐）。例如，人人网上出现“你可能认识的人”。如何实现？有一个非常简单的方法。如果说小刚和小明不是好朋友，但是他们有很多共同的朋友。那么可以认为A和B很可能认识。

如何使用Map/Reduce推荐好友

从图论的角度来看，就是先列出一个人的所有好友（记为小A），然后求小A和这些人之间有多少条长度为2的路径。只需对这些频道号进行排序并找到带有最高的。

所以我们Map/Reduce的任务就是找到每个人的前十名“推荐好友”。

社交网络图通常非常简单。我们假设输入按名称排序。

“瑞奇” => [“杰伊”,“彼得”,“菲利斯”]

“彼得”=> [“戴夫”,“杰克”,“瑞奇”, "susan"]

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

第一轮MR任务

本任务的目的是计算每对距离为2的人之间的路径条数。

中在Map函数中，我们首先为每对朋友制作笛卡尔积。不清楚。例如，

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

结果是

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

他们都是通过 Ricky 的牵线搭桥认识的。过滤掉已经是朋友的群组，然后对它们进行排序。传递给Reducer。

在Reduce函数中，必须将相同的组合传递给Reducer。所以他的Reducer只需要统计有多少个相同的组合传递给他即可。

​输入记录… person -> connection_list

​例如"ricky" => ["jay", "john", "mitch", "peter"]

连接列表也按字母顺序排序

def map(person, connection_list)

# 使用嵌套循环为connection_list中的每个friend1计算笛卡尔积

# 消除所有2度对（如果已经存在）

# 有一个单度连接

：emit([person,friend1, 0])

：对于connection_list中的每个friend2>friend1

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

：defpartition(key)

：#使用key的前两个元素来选择一个reducer

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

def reduce(person_pair,Frequency_list)

# 检查这是否是一个新的对

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

【跳过所有后续内容】如果这两个成对person

#已经认识对方

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

if !skip

path_count = 0

对于Frequency_list中的每个计数

path_count += count

【emit(person_pair, path_count)

【输出记录… person_pair = > path_count

<例如["jay", "john"] => 5

如何使用Map/Reduce推荐好友

第二轮MR任务

本轮MR任务的任务就是列出每个距离为2个朋友的人，找出他们可以直接走多少条路。

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

在Reduce函数中，只要每个人可能的朋友都是Just按它们之间的路径数排序。

输入记录 = 第 1 轮的输出记录

def map(person_pair, path_count)

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

defpartition(key)

#使用key的第一个元素来选择reducer

return super.partition(key[0])

def reduce(connection_count_pair, Candidate_list)

# 检查这是否是一个新人

if@current_person !=connection_count_pair[0]

emit(@current_person,@top_ten)

@top_ten = []

@current_person=connection_count_pair[0]

​#选择要连接的前十个候选者

​if @top_ten.size < 10​对于candidate_list中的每个候选者​@top_ten.append([candidate, connection_count_pair[1]])​break if @pick_count > 10

输出记录… person -> Candidate_count_list

例如"ricky" => [["jay", 5], ["peter", 3] …]

​关注者推荐

如果我想进行关注者推荐而不是朋友怎么办推荐？

很简单。只需将第一步中的MR任务改为求“Follow关系”和“Followed”关系的笛卡尔积即可。这里不再列出伪代码。

感谢您的阅读。以上是《何《如何使用Map/Reduce推荐好友》。经过文章的学习，相信大家对如何使用Map/Reduce推荐好友有了清晰的认识，对好友推荐的问题有了更深入的了解，具体的使用方法需要在实践中验证，这里小编将为大家推送更多相关知识点的文章，欢迎关注！