金 欣，王 晶，沈奇威

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

整個算法由一次mapreduce過程就可以完成。在map中對所有點依次進行處理，每個點的處理過程如下。

·遍歷該點的所有鄰居，以鄰居的ID為鍵，以點對象本身為值輸出記錄。

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

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

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

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

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

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

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

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

·一個點如果有很多的鄰居，為了找到所有相連的邊，對每一個鄰居的邊都要進行一次完整的遍歷，在遍歷過程中有很多是不必要的。

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

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

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

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

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

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

5 算法比較

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

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

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

6 結(jié)束語

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

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

2楊戈，廖建新，朱曉民等.流媒體分發(fā)系統(tǒng)關(guān)鍵技術(shù)綜述.電子學報，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