Hadoop實例：二度人脈與好友推薦
在新浪微博、人人網等社交網站上，為了使用戶在網絡上認識更多的朋友，社交網站往往提供類似“你可能感興趣的人”、“間接關注推薦”等好友推薦的功能。一直很好奇這個功能是怎么實現的。
其實，社交網站上的各個用戶以及用戶之間的相互關注可以抽象為一個圖。以下圖為例：
頂點A、B、C到I分別是社交網站的用戶，兩頂點之間的邊表示兩頂點代表的用戶之間相互關注。那么如何根據用戶之間相互關注所構成的圖，來向每個用戶推薦好友呢？可能大家都聽說過六度人脈的說法，所謂六度人脈是指：地球上所有的人都可以通過五層以內的熟人鏈和任何其他人聯系起來。通俗地講：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過六個人你就能夠認識任何一個陌生人。”這個理論在社交網絡中同樣成立。
現在我們以上圖為例，介紹下如何利用用戶之間相互關注所構成的圖，來向每個用戶推薦好友。首先我們不得不假設的是如果兩用戶之間相互關注，那么我們認為他們認識或者說是現實中的好友，至少應該認識。假設我們現在需要向用戶I推薦好友，我們發現用戶I的好友有H、G、C。其中H的好友還有A，G的好友還有 F，C的好友還有B、F。那么用戶I、H、G、C、A、B、F極有可能是同一個圈子里的人。我們應該把用戶A、B、F推薦給用戶I認識。進一步的想，用戶 F跟兩位I的好友C、G是好友，而用戶A、B都分別只跟一位I的好友是好友，那么相對于A、B來說，F當然更應該推薦給用戶I認識。
可能你會發現，在上面的分析中，我們使用了用戶I的二度人脈作為他的推薦好友，而且我們對用戶I的每個二度人脈進行了投票處理，選舉出***推薦。其實，我覺得，二度人脈的結果只能看看某個用戶的在社交網站上的人際關系鏈，而基于投票選舉產生的二度人脈才是好友推薦功能中所需要的好友。
另外你也可能已經認識到所謂的N度人脈，其實就是圖算法里面的寬度優先搜索。寬度優先搜索的主要思想是From Center To Outer，我們以用戶I為起點，在相互關注所構成的圖上往外不退回地走N步所能到的頂點，就是用戶I的N度好友。
下面是Python寫的N度人脈的算法，可以輸出某個用戶的N度好友,代碼詳見這里。
下面幾點是其與寬度優先搜索的不同之處：
1. 寬度優先搜索搜索的是起始頂點可達的所有頂點，N度人脈不需要，它只需要向外走N步，走到N步的頂點處便停止，不需要再往外走了。
2. 走過N步之后，結果中包含起始頂點往外走1、2……N-1步所能到達的所有頂點，返回結果之前需將這些點刪除。
3. 變量pathLenFromStart記錄這N步具體的走法。
上訴的算法看似可行，其實在實際中并不適用。社交網站上的用戶量至少是***別的，不可能把所有用戶之間相互關注的關系圖放進內存中，這個時候就可以依賴 Hadoop了。下面的實例中，我們的輸入是deg2friend.txt，保存用戶之間相互關注的信息。每行有兩個用戶ID，以逗號分割，表示這兩個用戶之間相互關注即認識。
二度好友的計算需要兩輪的MapReduce。***輪MapReduce的Map中，如果輸入是“H，I”，我們的輸出是 key=H，value=“H，I”跟key=I，value=“H，I”兩條結果。前者表示I可以通過H去發現他的二度好友，后者表示H可以通過I去發現他的二度好友。
根據***輪MapReduce的Map，***輪MapReduce的Reduce 的輸入是例如key =I，value={“H，I”、“C，I”、“G，I”} 。其實Reduce 的輸入是所有與Key代表的結點相互關注的人。如果H、C、G是與I相互關注的好友，那么H、C、G就可能是二度好友的關系，如果他們之間不是相互關注的。對應最上面的圖，H與C是二度好友，G與C是二度好友，但G與H不是二度好友，因為他們是相互關注的。***輪MapReduce的Reduce的處理就是把相互關注的好友對標記為一度好友（“deg1friend”）并輸出，把有可能是二度好友的好友對標記為二度好友（“deg2friend”）并輸出。
第二輪MapReduce則需要根據***輪MapReduce的輸出，即每個好友對之間是否是一度好友（“deg1friend”），是否有可能是二度好友（“deg2friend”）的關系，確認他們之間是不是真正的二度好友關系。如果他們有deg1friend的標簽，那么不可能是二度好友的關系；如果有deg2friend的標簽、沒有deg1friend的標簽，那么他們就是二度好友的關系。另外，特別可以利用的是，某好友對deg2friend標簽的個數就是他們成為二度好友的支持數，即他們之間可以通過多少個都相互關注的好友認識。
兩輪MapReduce的代碼，詳見這里。
根據上述兩輪的MapReduce的方法，我以部分微博的數據進行了測試，測試的部分結果如下：
通過與我(@Intergret)相互關注的138位好友，兩輪的MapReduce向我推薦的二度好友前三位是：2010963993（@可樂要改變），2022127621（@琥珀露珠）和2572979357（@趙鴻澤），他們都是我本科的同學，有很多共同的好友，但我跟他們三目前尚未相互關注，所以推薦結果還算靠譜。
