SNS网站都有一个功能，就是好友推荐(或者Follower推荐)。例如，在人人网上出现的“你可能认识的人”。怎么来实现呢，有一个很简单的办法。如果小刚和小明不是好友，但是他们有很多的共同好友。那么可以认为，A和B很可能相识。
从图论的讲法上看，就是先列出一个人(记为小A)的所有朋友的朋友，在寻找小A和这些人之间有多少长度为2的通路。将这些通路数排序，寻找最高的那几个就可以了。
所以我们的Map/Reduce的任务就是：找出所有人的十个Top“推荐好友”。
社会化网络的图一般都很简单。我们假设输入是按name排序的。
| 12 | "ricky" => ["jay", "peter", "phyllis"]"peter" => ["dave", "jack", "ricky", "susan"] |
我们使用两轮Map/Reduce任务来完成这个操作。
第一轮MR任务
这个任务的目的是计算每一对距离是2的人之间的通路数。
- 在Map函数中，我们先将每对朋友做一个笛卡尔乘积，说的不大清楚，举个例子，比如
1 "ricky"=>["jay","john","mitch"]
那么结果就是
1 ["jay", "john"], ["jay", "mitch"], ["john", "mitch"]
他们都是通过ricky牵线搭桥认识的。将已经是朋友的组合筛选掉，再排好序。传给Reducer。 - 在Reduce函数中, 相同的组合必定会传给Reducer。所以Reducer只要数好有几个相同的组合传给他就行了.
| 123456789101112131415161718192021222324252627282930313233 | Inputrecord... person->connection_liste.g."ricky"=>["jay","john","mitch","peter"]alsotheconnectionlistissortedbyalphabeticalorder defmap(person,connection_list) # Compute a cartesian product using nested loops foreachfriend1inconnection_list # Eliminate all 2-degree pairs if they already # have a one-degree connection emit([person,friend1,0]) foreachfriend2>friend1inconnection_list emit([friend1,friend2,1], 1) defpartition(key) #use the first two elements of the key to choose a reducer returnsuper.partition([key[0],key[1]]) defreduce(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=trueifperson_pair[2]==0 if!skip path_count=0 foreachcountinfrequency_list path_count+=count emit(person_pair,path_count) Outputrecord...person_pair=>path_counte.g.["jay","john"]=>5 |
第二轮MR任务
这一轮的MR任务是为了列出每个人距离为2的好友，查出他们直接究竟有几条路径。
- 在Map函数中，我们将每一组数据重新排列，保证一个人信息落在一个reducer上
- 在Reduce函数中，只要将每个人的可能好友之间的路径数排个序就可以了.
| 12345678910111213141516171819202122232425 | Inputrecord=Outputrecordofround1 defmap(person_pair,path_count) emit([person_pair[0],path_count],person_pair[1]) defpartition(key) #use the first element of the key to choose a reducer returnsuper.partition(key[0]) defreduce(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 foreachcandidateincandidate_list @top_ten.append([candidate,connection_count_pair[1]]) breakif@pick_count>10 Outputrecord...person->candidate_count_list e.g. "ricky"=>[["jay",5], ["peter",3]...] |
Follower推荐
如果我想要做Follower推荐而不是好友推荐怎么办呢？
很简单。只要将第一步的MR任务改为求“Follow关系”和“Followed”关系的笛卡尔乘积就可以了。这里就不列伪码了。
参考地址：http://horicky.blogspot.com/
jaogoy 这个应用只需要一轮mapreduce就可以完成：
1、在mapper输出时，设置partitioner为按friend1来分桶，于是同一个friend1的就到一个reducer中了
2、reducer中，对同一个friend1且同friend2的求count，并且保存到一个top_ten数组，当有新的的count大于top_ten中的最小count时，进行替代。最终得到friend1的top_ten
说明：
1、mapper中可以同时输出(friend1,friend2),(friend2,friend1)
2、mapper中可以输出介绍人，在reducer中将每个pair的介绍人求和
yankay 好主意。我也觉得第二次MR有一些鸡肋，但没能去掉。
Thanks