MapReduce实现二度好友关系
一、问题定义 我在网上找了些,关于二度人脉算法的实现,大部分无非是通过广度搜索算法来查找,犹豫深度已经明确了2以内;这个算法其实很简单,第一步找到你关注的人;第二步找到这些人关注的人,最后找出第二步结果中出现频率最高的一个或多个人(频率这块没完成),即完成。 但如果有千万级别的用户,那在运算时,就肯定会把这些用户的follow 关系放到内存中,计算的时候依次查找;先说明下我没有明确的诊断对比,这样做的效果一定没 基于hadoop实现的好;只是自己,想用hadoop实现下,最近也在学;若有不足的地方还请指点。 任务是求其其中的二度人脉、潜在好友,也就是如下图: 比如I认识C、G、H,但C不认识G,那么C-G就是一对潜在好友,但G-H早就认识了,因此不算为潜在好友。 那么一个关键问题是如何输入输入。 首先是五项五环图,可以看出共有13条边,那么输入数据也有13条就够了,比如说先输入AB,那么轮到b时候就不输入BA了,级变速如也没关系,因为会去重。 二、原理分析 首先,我们进行第一个MapReduce,同样是一个输入行,产生一对互逆的关系,压入context,例如Tom Lucy这...