最近做了一個項目，要求找出二度人脈的一些關系，就好似新浪微博的“你可能感興趣的人” 中，間接關注推薦；簡單描述：即你關注的人中有N個人同時都關注了 XXX 。

在程序的實現(xiàn)上，其實我們要找的是：若 User1 follow了10個人 ｛User3，User4，User5，... ，User12｝記為集合UF1，那么 UF1中的這些人，他們也有follow的集合，分別是記為： UF3（User3 follow的人），UF4，UF5，...，UF12；而在這些集合肯定會有交集，而由最多集合求交產(chǎn)生的交集，就是我們要找的：感興趣的人。

我在網(wǎng)上找了些，關于二度人脈算法的實現(xiàn)，大部分無非是通過廣度搜索算法來查找，猶豫深度已經(jīng)明確了2以內；這個算法其實很簡單，***步找到你關注的人；第二步找到這些人關注的人，***找出第二步結果中出現(xiàn)頻率***的一個或多個人，即完成。

但如果有***別的用戶，那在運算時，就肯定會把這些用戶的follow 關系放到內存中，計算的時候依次查找；先說明下我沒有明確的診斷對比，這樣做的效果一定沒 基于hadoop實現(xiàn)的好；只是自己，想用hadoop實現(xiàn)下，最近也在學；若有不足的地方還請指點。

首先，我的初始數(shù)據(jù)是文件，每一行為一個follow 關系 ida+‘\t’+idb；表示 ida follow idb。其次，用了2個Map/Reduce任務。

Map/Reduce 1：找出 任意一個用戶 的 follow 集合與 被 follow 的集合。如圖所示：

代碼如下：

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;} 

其中Separator.TABLE_String為自定義的分隔符；TextPair為自定義的 Writable 類，讓一個key可以對應兩個value，且這兩個value可區(qū)分。

Map/Reduce 2：在上一步關系中，若B follow A，而 A follow T ，則可以得出 T 為 B 的二度人脈，且 間接者為A ，于是找出 相同二度人脈的不同間接人。如圖所示：

代碼如下：

Map 任務：輸出時 key 為 由兩個String 記錄的ID表示的 二度人脈關系，value 為 這個二度關系產(chǎn)生的間接人的ID

public void map(Text key, TextPair values, Context context) throws IOException,InterruptedException{  
        Map<String, String> first_follow = new HashMap<String, String>();  
        Map<String, String> second_befollow = new HashMap<String, String>();  
        String _key = key.toString();  
        String[] follow = values.getFirst().toString().split(Separator.TABLE_String);  
          
        String[] second = values.getSecond().toString().split(Separator.TABLE_String);  
          
        for(String sf : follow){  
              
            first_follow.put(sf , _key );  
              
        }  
          
        for(String ss : second){  
              
            second_befollow.put(ss , _key );  
              
        }  
          
        for(Entry<String, String> f : first_follow.entrySet()){  
            for(Entry<String, String> b : second_befollow.entrySet()){  
                context.write(new TextPair(f.getKey() ,b.getKey()), new Text(key));  
            }  
        }  
&nbsp;&nbsp;&nbsp;&nbsp;} 

Reduce任務：輸出時 key 仍然為二度人脈關系， value 為所有間接人 的ID以逗號分割。

protected void reduce(TextPair key, Iterable<Text> values, Context context)  
    throws IOException, InterruptedException {  
      
    StringBuilder resutl = new StringBuilder();  
    for (Text text : values){  
        resutl.append(text.toString()).append(",");  
    }  
      
    context.write(key, new Text(resutl.toString()));  
} 

到這步，二度人脈關系基本已經(jīng)挖掘出來，后續(xù)的處理就很簡單了，當然也基于二度人脈挖掘三度，四度：）

原文鏈接：http://my.oschina.net/BreathL/blog/75112