海量数据的二度人脉挖掘算法（Hadoop 实现）

作者：用户投稿来源：网络发布时间： 13/01/12

最近做了一个项目，要求找出二度人脉的一些关系，就好似新浪微博的“你可能感兴趣的人” 中，间接关注推荐；简单描述：即你关注的人中有N个人同时都关注了 XXX 。

在程序的实现上，其实我们要找的是：若 User1 follow了10个人｛User3，User4，User5，... ，User12｝记为集合UF1，那么 UF1中的这些人，他们也有follow的集合，分别是记为： UF3（User3 follow的人），UF4，UF5，...，UF12；而在这些集合肯定会有交集，而由最多集合求交产生的交集，就是我们要找的：感兴趣的人。

我在网上找了些，关于二度人脉算法的实现，大部分无非是通过广度搜索算法来查找，犹豫深度已经明确了2以内；这个算法其实很简单，第一步找到你关注的人；第二步找到这些人关注的人，最后找出第二步结果中出现频率最高的一个或多个人，即完成。

但如果有千万级别的用户，那在运算时，就肯定会把这些用户的follow 关系放到内存中，计算的时候依次查找；先说明下我没有明确的诊断对比，这样做的效果一定没基于hadoop实现的好；只是自己，想用hadoop实现下，最近也在学；若有不足的地方还请指点。

首先，我的初始数据是文件，每一行为一个follow 关系 ida+‘\t’+idb；表示 ida follow idb。其次，用了2个Map/Reduce任务。

Map/Reduce 1：找出任意一个用户的 follow 集合与被 follow 的集合。如图所示：

498)this.width=498;'' onmousewheel = ''javascript:return big(this)'' style="cursor: pointer" alt="" src="/uploadfile/201301/12/F7121746140.jpg" />

代码如下：

Map任务：输出时 key ：间接者 A 的ID ，value：follow 的人的ID 或被follow的人的ID

public void map(Text key, IntWritable values, Context context) throws IOException,InterruptedException{  
        int value = values.get();  
        //切分出两个用户id  
        String[] _key = Separator.CONNECTORS_Pattern.split(key.toString());  
        if(_key.length ==2){  
            //"f"前缀表示 follow；"b" 前缀表示 被follow  
            context.write(new Text(_key[0]), new Text("f"+_key[1]));  
            context.write(new Text(_key[1]), new Text("b"+_key[0]));  
              
              
        }  
    }

Reduce任务：输出时 key ：间接者 A 的ID ， value为两个String，第一个而follow的所有人（用分割符分割），第二个为被follow的人（同样分割）

&nbsp;&nbsp;&nbsp;&nbsp;protected void reduce(Text key, Iterable<TextPair> pairs, Context context)  
     throws IOException,InterruptedException{  
        StringBuilder first_follow = new StringBuilder();  
        StringBuilder second_befollow = new StringBuilder();  
          
        for(TextPair pair: pairs){  
            String id = pair.getFirst().toString();  
            String value = pair.getSecond().toString();  
            if(id.startsWith("f")){  
                first_follow.append(id.substring(1)).append(Separator.TABLE_String);  
            } else if(id.startsWith("b")){  
                second_befollow.append(id.substring(1)).append(Separator.TABLE_String);  
            }  
        }  
          
        context.write(key, new TextPair(first_follow.toString(),second_befollow.toString()));  
&nbsp;&nbsp;&nbsp;&nbsp;}