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