金 欣，王 晶，沈奇威

(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京100876；東信北郵信息技術(shù)有限公司 北京100191)

1 概述

隨著社會(huì)的發(fā)展和技術(shù)的進(jìn)步，人與人之間的聯(lián)系越來(lái)越緊密，手機(jī)正是一種為了滿足人們互相溝通需求而出現(xiàn)的工具。根據(jù)工業(yè)和信息化部2010年2月公布的數(shù)據(jù)，中國(guó)的手機(jī)用戶已經(jīng)達(dá)到了7.74億[1]，而在這個(gè)龐大的數(shù)字之后，慢慢浮現(xiàn)出來(lái)的是更加豐富的用戶需求，用戶不僅僅滿足于打電話、發(fā)短信，各種數(shù)據(jù)業(yè)務(wù)正在飛速走進(jìn)我們的生活，如手機(jī)閱讀、多媒體業(yè)務(wù)、移動(dòng)廣告等。

隨著數(shù)據(jù)業(yè)務(wù)的不斷豐富和電信運(yùn)營(yíng)商之間的競(jìng)爭(zhēng)愈發(fā)激烈，提供更好的服務(wù)，提高用戶體驗(yàn)成為降低用戶流失、保證市場(chǎng)份額的關(guān)鍵。然而，如何提供更好的服務(wù)呢？通過(guò)對(duì)用戶數(shù)據(jù)的分析了解用戶喜好，并向用戶提供個(gè)性化的信息服務(wù)是最主要的方式之一。通過(guò)數(shù)據(jù)挖掘的方式，電信運(yùn)營(yíng)商可以了解用戶的個(gè)人喜好、消費(fèi)傾向等，利用這些信息，在提高服務(wù)質(zhì)量的同時(shí)努力實(shí)現(xiàn)精準(zhǔn)的廣告投放增加收益。如何高效地對(duì)數(shù)以億計(jì)的手機(jī)用戶的個(gè)人數(shù)據(jù)、業(yè)務(wù)數(shù)據(jù)、通話數(shù)據(jù)等進(jìn)行處理，成為運(yùn)營(yíng)商面臨的新挑戰(zhàn)。

社會(huì)網(wǎng)絡(luò)分析是數(shù)據(jù)挖掘的一個(gè)分支，它通過(guò)分析人與人之間的關(guān)聯(lián)尋找有價(jià)值的信息。自中心網(wǎng)絡(luò)是指以個(gè)人為中心的社會(huì)網(wǎng)絡(luò)，通過(guò)分析個(gè)人與周圍環(huán)境的交互來(lái)挖掘個(gè)人特征。手機(jī)本身就是人們之間溝通的工具，運(yùn)用社會(huì)網(wǎng)絡(luò)分析方法對(duì)手機(jī)用戶的通話網(wǎng)絡(luò)、短信網(wǎng)絡(luò)等進(jìn)行分析是利用數(shù)據(jù)挖掘?qū)ふ矣脩籼卣鞯闹匾侄巍?/p>

本文將逐步設(shè)計(jì)基于hadoop分布式計(jì)算平臺(tái)的自中心網(wǎng)絡(luò)生成算法實(shí)現(xiàn)，該算法針對(duì)mapreduce的分布式計(jì)算模型，從數(shù)據(jù)分布、IO等方面對(duì)算法進(jìn)行改進(jìn)，最終給出一種適合mapreduce的高效、自中心網(wǎng)絡(luò)生成算法。

2 社會(huì)網(wǎng)絡(luò)分析和自中心網(wǎng)絡(luò)

傳統(tǒng)的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)處理的對(duì)象是單獨(dú)的數(shù)據(jù)實(shí)例，這些數(shù)據(jù)實(shí)例往往可以用一個(gè)包含多個(gè)屬性值的向量來(lái)表示，同時(shí)假設(shè)這些數(shù)據(jù)實(shí)例之間是統(tǒng)計(jì)上獨(dú)立的。而社會(huì)網(wǎng)絡(luò)分析以人為個(gè)體，通過(guò)分析人與人之間的關(guān)聯(lián)尋找網(wǎng)絡(luò)和個(gè)人特征。社會(huì)網(wǎng)絡(luò)分析分為兩個(gè)部分：一是對(duì)網(wǎng)絡(luò)整體進(jìn)行分析，例如對(duì)分群、網(wǎng)絡(luò)演變等的研究；二是自中心網(wǎng)絡(luò)，就是以個(gè)人為中心通過(guò)分析其與周圍環(huán)境的交互來(lái)分析其特征。由于自中心網(wǎng)絡(luò)的分析可以挖掘出個(gè)人的特征，相比整體網(wǎng)絡(luò)分析更加適合個(gè)人喜好、消費(fèi)傾向、騷擾電話分析等信息的挖掘。

相比f(wàn)acebook等構(gòu)建的社會(huì)網(wǎng)絡(luò)，手機(jī)用戶構(gòu)建的網(wǎng)絡(luò)更加生活化和真實(shí)，因此對(duì)社會(huì)網(wǎng)絡(luò)分析具有更大的價(jià)值。隨著手機(jī)用戶的不斷增多和移動(dòng)業(yè)務(wù)的不斷豐富，人與人之間的交互越來(lái)越復(fù)雜，用戶交互數(shù)據(jù)無(wú)論從維度上還是數(shù)量上都對(duì)移動(dòng)運(yùn)營(yíng)商的數(shù)據(jù)分析工作提出了挑戰(zhàn)。近年來(lái)分布式計(jì)算技術(shù)的高速發(fā)展為這種海量數(shù)據(jù)分析的應(yīng)用提出了新的解決方案，并且隨著分布式計(jì)算技術(shù)的愈發(fā)成熟，其在移動(dòng)領(lǐng)域的應(yīng)用也越來(lái)越多[2]。通過(guò)將用戶數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)上進(jìn)行分布計(jì)算可以顯著提高運(yùn)算速度，特別是對(duì)于自中心網(wǎng)絡(luò)，由于是以每個(gè)用戶為中心來(lái)分析數(shù)據(jù)的，因此更加適合通過(guò)分布式方式進(jìn)行計(jì)算。由于社會(huì)網(wǎng)絡(luò)分析是通過(guò)數(shù)據(jù)之間的關(guān)聯(lián)進(jìn)行的，所以用戶與用戶之間的數(shù)據(jù)傳遞會(huì)使得系統(tǒng)的IO消耗十分嚴(yán)重，這是研究分布式社會(huì)網(wǎng)絡(luò)分析算法必須要解決的問(wèn)題。

3 基于mapreduce的傳統(tǒng)自中心網(wǎng)絡(luò)生成算法

mapreduce是一種計(jì)算模型，每個(gè)mapreduce分為一個(gè)map過(guò)程和一個(gè)reduce過(guò)程，map和reduce的輸入、輸出數(shù)據(jù)采用鍵值對(duì)的方式進(jìn)行描述，map會(huì)對(duì)每一個(gè)鍵值對(duì)進(jìn)行處理，處理結(jié)果用鍵值對(duì)的形式進(jìn)行輸出，輸出結(jié)果相同鍵值的會(huì)匯總到一起，由reduce進(jìn)行處理。詳細(xì)的mapreduce編程模型介紹可以參照參考文獻(xiàn)[3]。

算法的存儲(chǔ)模型采用以點(diǎn)為基礎(chǔ)存儲(chǔ)整個(gè)社會(huì)網(wǎng)絡(luò)圖。每個(gè)點(diǎn)被分配一個(gè)ID，用一個(gè)對(duì)象表示。這個(gè)對(duì)象除了存儲(chǔ)點(diǎn)的ID之外，還有與該點(diǎn)所有相連的邊。對(duì)象表示的點(diǎn)本身為中心點(diǎn)，邊用除了中心點(diǎn)之外的另外一個(gè)點(diǎn)來(lái)表示，這樣就可以構(gòu)成一個(gè)完整的社會(huì)網(wǎng)絡(luò)圖。

一個(gè)點(diǎn)的自中心網(wǎng)絡(luò)由兩部分組成：一是所有與自己相連的點(diǎn)，二是這些點(diǎn)之間的邊。任何一個(gè)自中心網(wǎng)絡(luò)算法都要首先找出每個(gè)點(diǎn)所在的自中心網(wǎng)絡(luò)。在現(xiàn)有的存儲(chǔ)模型中，對(duì)于一個(gè)點(diǎn)對(duì)象來(lái)說(shuō)，已經(jīng)存儲(chǔ)了自己中心網(wǎng)絡(luò)中的點(diǎn)以及和自己相連的邊，因此，自中心網(wǎng)絡(luò)生成工作的核心就是找到這個(gè)點(diǎn)的鄰居之間的邊。傳統(tǒng)的自中心網(wǎng)絡(luò)生成算法就是遍歷自己所有鄰居的鄰居來(lái)找到自己鄰居之間相連的邊，下面給出傳統(tǒng)自中心網(wǎng)絡(luò)算法的分布式實(shí)現(xiàn)。

整個(gè)算法由一次mapreduce過(guò)程就可以完成。在map中對(duì)所有點(diǎn)依次進(jìn)行處理，每個(gè)點(diǎn)的處理過(guò)程如下。

·遍歷該點(diǎn)的所有鄰居，以鄰居的ID為鍵，以點(diǎn)對(duì)象本身為值輸出記錄。

·以自身點(diǎn)ID為鍵，對(duì)象本身為值輸出數(shù)據(jù)。

經(jīng)過(guò)map過(guò)程，reduce接收到的每個(gè)鍵值對(duì)應(yīng)的是中心點(diǎn)和它的所有鄰居，鄰居對(duì)象包含了這個(gè)鄰居的邊信息。通過(guò)將鄰居對(duì)象和中心點(diǎn)對(duì)象的邊進(jìn)行比較可以找到該鄰居與中心點(diǎn)其他鄰居之間是否有邊存在。最終，我們可以找到所有相連的鄰居，從而形成該點(diǎn)的自中心網(wǎng)絡(luò)，如圖1所示。

A至F是其中的6個(gè)點(diǎn)，設(shè)A至F代表的是點(diǎn)對(duì)象，而a至f是點(diǎn)的ID，則在map中，A會(huì)輸出5條鍵值對(duì)分別為a→A、c→A、d→A、e→A、f→A；在reduce中，a對(duì)應(yīng)的數(shù)組包含的是(A，C，D，E，F(xiàn))，通過(guò)對(duì)這些對(duì)象的邊信息的遍歷，可以找到3條邊，結(jié)合A對(duì)象中的信息，生成以A為中心點(diǎn)的自中心網(wǎng)絡(luò)。

由于在reduce中相同鍵值下的數(shù)據(jù)排序不能確定，所以不能知道哪一個(gè)是中心點(diǎn)，所以不得不將所有數(shù)組中的數(shù)據(jù)先存儲(chǔ)在內(nèi)存中，然后通過(guò)將每個(gè)對(duì)象的ID和鍵值進(jìn)行比較，相等的就是中心點(diǎn)。這種方式在一個(gè)點(diǎn)有很多鄰居的情況下會(huì)導(dǎo)致內(nèi)存消耗非常嚴(yán)重。這個(gè)問(wèn)題可以用mapreduce中常用的技巧secondary sort[4]來(lái)解決，這里不再詳述。

4 基于尋找三角形的分布式自中心網(wǎng)絡(luò)生成算法設(shè)計(jì)與實(shí)現(xiàn)

§3描述的算法是自中心網(wǎng)絡(luò)生成算法基于mapreduce的一個(gè)直接而簡(jiǎn)單的實(shí)現(xiàn)，該算法有3個(gè)明顯的不足。

·mapreudce程序的主要瓶頸在IO，而社會(huì)網(wǎng)絡(luò)分析算法的IO消耗也是非常嚴(yán)重的。在這個(gè)算法中傳輸了許多不必要的信息，比如點(diǎn)C以a為鍵輸出的數(shù)據(jù)是為了生成以A為中心的自中心網(wǎng)絡(luò)，由于傳輸?shù)氖菍?duì)象，所有該點(diǎn)的鄰居信息，包括B都在對(duì)象中，但實(shí)際上是不需要的，由于其不了解A的情況，所以不能判斷哪些邊是冗余的。在一個(gè)龐大的網(wǎng)絡(luò)中，這種不必要的數(shù)據(jù)將是非常巨大的，大大影響了系統(tǒng)的IO負(fù)載，降低了算法的性能。

·分布式算法的效率和數(shù)據(jù)的分布有很大關(guān)系。根據(jù)參考文獻(xiàn)[5]分析，在一個(gè)真實(shí)的網(wǎng)絡(luò)中，往往有很少的一些點(diǎn)，這些點(diǎn)的度數(shù)非常大，在一個(gè)龐大的社會(huì)網(wǎng)絡(luò)圖中點(diǎn)的度數(shù)呈指數(shù)分布?！?描述的算法由于以中心點(diǎn)為計(jì)算的核心，必然會(huì)因?yàn)橐恍┒葦?shù)很大的點(diǎn)使得某些點(diǎn)的計(jì)算量非常大，從而影響整個(gè)程序的執(zhí)行效率。

·一個(gè)點(diǎn)如果有很多的鄰居，為了找到所有相連的邊，對(duì)每一個(gè)鄰居的邊都要進(jìn)行一次完整的遍歷，在遍歷過(guò)程中有很多是不必要的。

可以看出，這些缺陷都是由于算法實(shí)現(xiàn)采用基于中心點(diǎn)遍歷鄰居的方式導(dǎo)致的。這種方式由于圖中點(diǎn)的差異必然導(dǎo)致數(shù)據(jù)分布的不均衡，而由于在每個(gè)點(diǎn)的處理過(guò)程中的重復(fù)且復(fù)雜的計(jì)算，使得單點(diǎn)負(fù)載嚴(yán)重影響性能。

因此，需要換一種思路才能解決上述問(wèn)題。一個(gè)點(diǎn)的鄰居如果相連，那么這兩個(gè)相連的鄰居和中心點(diǎn)就可以構(gòu)成一個(gè)三角形。如果找到與一個(gè)點(diǎn)相關(guān)的所有三角形，就相當(dāng)于找到了所有屬于該點(diǎn)自中心網(wǎng)絡(luò)的邊。通過(guò)參考文獻(xiàn)[6]的介紹可以看出，找三角形這種操作實(shí)際上是將一個(gè)大的圖打散成為許多很小的部分，非常適合分布式計(jì)算。

基于以上分析提出了一種新的生成自中心網(wǎng)絡(luò)的算法。該算法首先要找出圖中的所有三角形，之后只要計(jì)算每個(gè)點(diǎn)存在于哪些三角形中，就可以判斷該點(diǎn)有哪些鄰居之間是相連的。

改進(jìn)后的算法需要兩個(gè)mapreduce過(guò)程，第一個(gè)mapreduce過(guò)程是找出所有三角形，第二個(gè)過(guò)程是通過(guò)三角形得到自中心網(wǎng)絡(luò)。

在第一個(gè)mapreduce過(guò)程中，在map中輸出一個(gè)點(diǎn)鄰居的所有鄰居對(duì)，以中心點(diǎn)和兩個(gè)鄰居用分隔符相連作為鍵，值為空。reduce中每個(gè)鍵對(duì)應(yīng)的相當(dāng)于是一個(gè)3個(gè)點(diǎn)組合。如果一個(gè)三角形存在，則這個(gè)組合會(huì)收到3條記錄。通過(guò)簡(jiǎn)單的計(jì)數(shù)就可以判斷這3個(gè)點(diǎn)在圖中是否可以組成三角形，如果可以，則將該記錄分別以3個(gè)點(diǎn)為鍵值輸出3條記錄。例如圖1，A點(diǎn)需要輸出6條記錄，每條記錄是一個(gè)字符串，而采用原算法需要輸出4條記錄，每條記錄都是保存該點(diǎn)所有邊信息的點(diǎn)對(duì)象。由于新思路沒(méi)有以點(diǎn)為中心來(lái)計(jì)算，所有的數(shù)據(jù)會(huì)更加均勻地分布在各個(gè)節(jié)點(diǎn)上，保證了負(fù)載的均衡，解決了單點(diǎn)負(fù)載問(wèn)題。實(shí)際上，這個(gè)過(guò)程可以優(yōu)化，如果3個(gè)點(diǎn)構(gòu)不成三角形，那么肯定只能接收到一條記錄，這樣利用ID排序可以為每個(gè)三角形只輸出兩條記錄，相當(dāng)于節(jié)省了三分之一的IO。通過(guò)這個(gè)mapreduce過(guò)程，可以得到和3個(gè)三角形。

在第二個(gè)mapreduce過(guò)程中，將原圖和第一個(gè)mapreduce運(yùn)算的結(jié)果同時(shí)作為輸入進(jìn)行一次計(jì)算，在reduce中一個(gè)點(diǎn)可以接收到許多三角形，每個(gè)三角形對(duì)應(yīng)一條邊，將這些邊匯總起來(lái)可以形成該點(diǎn)的自中心網(wǎng)絡(luò)。這個(gè)過(guò)程也有單點(diǎn)的問(wèn)題，但是由于運(yùn)算過(guò)程僅僅是簡(jiǎn)單存儲(chǔ)，所以負(fù)載問(wèn)題并不嚴(yán)重。

5 算法比較

為了比較兩種算法的性能，對(duì)算法進(jìn)行了測(cè)試。測(cè)試數(shù)據(jù)是某論壇數(shù)據(jù)，通過(guò)回帖信息建立起一個(gè)社會(huì)網(wǎng)絡(luò)。用戶數(shù)量為78 790，為了使得輸入會(huì)分布在不同的機(jī)器上，我們將其按大小均勻分為6個(gè)文件，相應(yīng)地使用3臺(tái)性能相同的機(jī)器搭建了一個(gè)hadoop集群，每臺(tái)機(jī)器可以同時(shí)執(zhí)行兩個(gè)map任務(wù)和兩個(gè)reduce任務(wù)。

使用原算法總共運(yùn)行時(shí)間為1 min 57 s，而使用找三角形方式兩步過(guò)程運(yùn)行時(shí)間總共為44 s。效率提升的原因主要有3個(gè)：一是map到reduce的IO，原算法為794 MB，新算法兩步總共為296 MB，IO消耗降低很明顯；二是原算法不同reduce之間運(yùn)行時(shí)間最短為1 min 18 s，最長(zhǎng)為1 min 42 s，運(yùn)行時(shí)間最長(zhǎng)的機(jī)器使得整個(gè)算法運(yùn)行時(shí)間延長(zhǎng)了24s，而新算法中不同reduce運(yùn)行時(shí)間相差不超過(guò)2s；三是由于算法的不同，每個(gè)reduce運(yùn)行時(shí)間都少了很多。

雖然這個(gè)數(shù)據(jù)量不是很大，但是可以明顯看出新的實(shí)現(xiàn)方式對(duì)算法性能的影響。如果數(shù)據(jù)量進(jìn)一步增大，那么由于IO和負(fù)載平衡的原因，新算法的優(yōu)勢(shì)將會(huì)更加明顯。新算法的優(yōu)勢(shì)在于利用了社會(huì)網(wǎng)絡(luò)的整體稀疏和度數(shù)指數(shù)分布的特點(diǎn)改進(jìn)了算法的IO和負(fù)載平衡，從而提高了算法性能。如果圖的密度很大，且所有點(diǎn)度數(shù)都很大，新算法的優(yōu)勢(shì)就不存在了，而且由于多了一個(gè)mapreduce過(guò)程，整個(gè)算法的性能可能還低于原算法，但是根據(jù)參考文獻(xiàn)[5]中的驗(yàn)證和分析，幾乎所有的真實(shí)網(wǎng)絡(luò)都是屬于前一種的。

6 結(jié)束語(yǔ)

本文針對(duì)真實(shí)的社會(huì)網(wǎng)絡(luò)特征和mapreduce分布式計(jì)算模型，提出了一種基于三角形查找的分布式自中心網(wǎng)絡(luò)生成算法，用于解決海量數(shù)據(jù)自中心網(wǎng)絡(luò)生成問(wèn)題。該算法在處理真實(shí)社會(huì)網(wǎng)絡(luò)過(guò)程中，很好地利用了真實(shí)網(wǎng)絡(luò)的分布特征，通過(guò)對(duì)IO和負(fù)載均衡的優(yōu)化大幅提高了算法性能。如果整個(gè)網(wǎng)絡(luò)是高密度且度數(shù)均勻分布的話，算法性能會(huì)低于直接的網(wǎng)絡(luò)生成算法。對(duì)于手機(jī)用戶構(gòu)建的真實(shí)的社會(huì)網(wǎng)絡(luò)的分析問(wèn)題，該算法的優(yōu)勢(shì)還是比較明顯的。

1 http://www.enicn.com/article/2010-02-04/0204610402010.shtml

2楊戈，廖建新，朱曉民等.流媒體分發(fā)系統(tǒng)關(guān)鍵技術(shù)綜述.電子學(xué)報(bào)，2009(1)：137～141

3 Jeffrey D，Sanjay G.Mapreduce：simplied data processing on large clusters.In：Proceedings of the 6th Symposium on Operating Systems Design and Implementation(OSDI04)，San Francisco，California，USA，December 2004

4 Venner J.Pro hadoop.USA：Berkely，2009

5 Albert R，Barabasi A L.Statistical mechanics of complex networks.Rev Mod Phys,2002(74)：10～97

6 Graph twiddling in a mapreduce world.Computing in Science and Engineering，2009，11(4)：29～41