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