在線社交網(wǎng)絡(luò)個體影響力算法測試與性能評估

全擁，賈焰，張良，朱爭，周斌，方濱興

?

在線社交網(wǎng)絡(luò)個體影響力算法測試與性能評估

全擁1，賈焰1，張良1，朱爭1，周斌1，方濱興2

（1. 國防科技大學(xué)計算機學(xué)院，湖南 長沙 410073；2. 北京郵電大學(xué)計算機學(xué)院，北京 100876）

社交影響力是驅(qū)動信息傳播的關(guān)鍵因素，基于在線社交網(wǎng)絡(luò)數(shù)據(jù)，可以對社交影響力進(jìn)行建模和分析。針對一種經(jīng)典的個體影響力計算方法，介紹了該算法的2種并行化實現(xiàn)，并在真實大規(guī)模在線社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了性能測試。結(jié)果表明，借助現(xiàn)有的大數(shù)據(jù)處理框架，顯著提高了個體影響力計算方法在海量數(shù)據(jù)集中的計算效率，同時也給該類算法的研究和優(yōu)化提供了實證依據(jù)。

性能測試；社交影響力；分布式計算；在線社交網(wǎng)絡(luò)

1 引言

隨著Web 2.0技術(shù)的進(jìn)一步完善以及移動智能終端的大量使用，在線社交網(wǎng)絡(luò)蓬勃發(fā)展。以新浪微博和Facebook為代表的在線社交網(wǎng)絡(luò)平臺逐漸成為網(wǎng)絡(luò)應(yīng)用的主流，并改變了人們生活和交流的方式。在線社交網(wǎng)絡(luò)中用戶之間的交互行為，使網(wǎng)絡(luò)世界與現(xiàn)實世界相互影響，特別是快速傳播擴(kuò)散的網(wǎng)絡(luò)信息能夠迅速形成社會輿論，對現(xiàn)實世界人們的行為產(chǎn)生直接影響[1]。社交影響力是用戶交互行為的內(nèi)在誘因，而交互行為是社交影響力的外在表現(xiàn)，從而對信息的傳播產(chǎn)生直接影響。社交影響力是社會影響力在線社交網(wǎng)絡(luò)中的自然延伸，而社會影響力被認(rèn)為是個人行為能夠直接或間接地影響他人的想法、感情以及行動[2]。因此，社交影響力可以通過用戶之間的社交活動體現(xiàn)出來，表現(xiàn)為在線社交網(wǎng)絡(luò)中用戶的行為和思想等受他人影響發(fā)生改變的現(xiàn)象[3]。

影響力分析是在線社交網(wǎng)絡(luò)分析的重要內(nèi)容，在輿情引導(dǎo)與社會運作中起著重要作用，具有廣泛應(yīng)用，例如信息推薦[4]、專家發(fā)現(xiàn)[5]、影響極大化[6]、病毒式營銷[7]等。作為社交影響力分析的主要內(nèi)容，個體影響力度量一直是學(xué)術(shù)界的研究熱點問題，主要是定量計算個體的影響力大小，通過排名技術(shù)發(fā)現(xiàn)在線社交網(wǎng)絡(luò)中的影響力個體。影響力個體在不同應(yīng)用中又可被稱為意見領(lǐng)袖[8]、領(lǐng)域?qū)＜襕5]等。最初，相關(guān)學(xué)者在社會網(wǎng)絡(luò)中發(fā)現(xiàn)了人們的影響力存在差異性，即具有廣泛影響力的個體更容易將自己的觀點傳達(dá)給其他人。同樣，在線社交網(wǎng)絡(luò)中的影響力用戶發(fā)布或評論的信息，更容易引發(fā)大量用戶的轉(zhuǎn)發(fā)和閱讀，如新浪微博中的大V用戶。因此，在線社交網(wǎng)絡(luò)中的影響力個體在創(chuàng)新采用、網(wǎng)絡(luò)群體聚集、信息傳播與導(dǎo)向等方面發(fā)揮著重要作用。但是，由于理論模型和實驗方法的限制，早期工作只能從小樣本數(shù)據(jù)集上定性地分析個體影響力，驗證了社會系統(tǒng)中個體影響力的存在性。在線社交網(wǎng)絡(luò)提供了豐富可用的實驗數(shù)據(jù)，研究者可以對用戶本身體現(xiàn)出來的影響力進(jìn)行建模和量化計算[9-11]。

實際上，由在線社交網(wǎng)絡(luò)數(shù)據(jù)構(gòu)建的圖結(jié)構(gòu)模型相當(dāng)復(fù)雜，一般包含上億個用戶節(jié)點、用戶之間關(guān)系構(gòu)成的成百上千億條邊以及他們產(chǎn)生的海量網(wǎng)絡(luò)信息，如截至2017年6月底，新浪微博的活躍用戶數(shù)已達(dá)3.65億。這對個體影響力計算方法提出了新的挑戰(zhàn)，難以在如此超大規(guī)模圖上高效度量在線社交網(wǎng)絡(luò)用戶的影響力。但是，不同類別大數(shù)據(jù)處理框架的出現(xiàn)使高效分析上述海量數(shù)據(jù)成為可能。首先，基于采用的小樣本數(shù)據(jù)集或子圖結(jié)構(gòu)，對個體影響力度量模型進(jìn)行分析和驗證。然后，結(jié)合具體的大數(shù)據(jù)處理框架，對個體影響力度量模型進(jìn)行并行化實現(xiàn)。最后，在集群環(huán)境中部署個體影響力并行化算法，高效地計算在線社交網(wǎng)絡(luò)用戶的影響力[12-14]。當(dāng)前，Apache基金會開發(fā)的一種開源的分布式基礎(chǔ)框架Hadoop應(yīng)用比較廣泛，它實現(xiàn)了一個用于存儲海量數(shù)據(jù)的分布式文件系統(tǒng)（HDFS）?；贖adoop平臺，本文選取MapReduce和Spark兩種并行計算模型來說明大數(shù)據(jù)處理框架對個體影響力度量算法的性能影響。針對真實的大規(guī)模在線社交網(wǎng)絡(luò)數(shù)據(jù)和不同的大數(shù)據(jù)處理框架下，實驗利用上述并行編程模型分別實現(xiàn)了一類經(jīng)典的個體影響力度量算法，并對不同規(guī)模數(shù)據(jù)集以及不同集群之間的算法性能進(jìn)行了比較。

2 個體影響力計算方法

在線社交網(wǎng)絡(luò)個體影響力度量算法主要從網(wǎng)絡(luò)結(jié)構(gòu)、用戶行為、交互信息等方面對用戶自身表現(xiàn)出的社交影響力進(jìn)行建模分析及量化計算。一般地，在線社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可由圖={,}表示，其中，是用戶集合，是用戶之間的關(guān)系構(gòu)成邊的集合。實際應(yīng)用中，當(dāng)用戶之間的關(guān)系是有向的，那么是有向圖，如轉(zhuǎn)發(fā)關(guān)系；當(dāng)用戶之間的關(guān)系是無向的，那么是無向圖，如好友關(guān)系。也可以是帶權(quán)圖，表示用戶和用戶之間形成邊的權(quán)重，如轉(zhuǎn)發(fā)頻率和好友親密度等。早期的個體影響力計算方法主要在拓?fù)浣Y(jié)構(gòu)圖中利用復(fù)雜網(wǎng)絡(luò)的相關(guān)概念來定量計算在線社交網(wǎng)絡(luò)中用戶的影響力，如圖中節(jié)點的出度與入度、度中心度[15]、接近中心度[16]、介數(shù)中心度[17]、?殼[18]等。這些方法表達(dá)的意義比較直觀，被廣泛應(yīng)用于在線社交網(wǎng)絡(luò)中用戶影響力的分析。例如，節(jié)點的出度與入度直接衡量了用戶對其鄰居用戶的影響力；度中心度衡量了用戶對其鄰居用戶的平均影響力；接近中心度衡量用戶對其他用戶的間接影響力；介數(shù)中心度和?殼都衡量了用戶在信息傳播擴(kuò)散過程中的影響力。但是這類基于網(wǎng)絡(luò)結(jié)構(gòu)的方法也有其局限性，沒有充分考慮用戶自身行為或用戶之間的交互信息等數(shù)據(jù)，導(dǎo)致最終計算的用戶影響力結(jié)果不夠精確。

為了準(zhǔn)確度量在線社交網(wǎng)絡(luò)中用戶的社交影響力，相關(guān)學(xué)者借鑒了經(jīng)典的網(wǎng)頁排名模型PageRank算法[19]，通過融合用戶屬性和網(wǎng)絡(luò)信息等因素，設(shè)計了多種個體影響力度量算法。PageRank算法最初被應(yīng)用于Google的搜索引擎中，是一種基于反向鏈接和正向鏈接分析的網(wǎng)頁排名算法。該算法利用一種基于馬爾可夫的隨機游走思想來模擬用戶瀏覽網(wǎng)頁的行為，并認(rèn)為一個網(wǎng)頁的重要性由所有鏈向它網(wǎng)頁的重要性決定。假設(shè)={,}是由互聯(lián)網(wǎng)中所有的網(wǎng)頁及其鏈接關(guān)系構(gòu)成的圖結(jié)構(gòu)，為網(wǎng)頁得分組成的向量，是由鏈接關(guān)系產(chǎn)生的轉(zhuǎn)移概率矩陣，則PageRank算法可用矩陣乘積的形式為

=MT+(1)

其中，為正則化因子，是修正項。最初的PageRank算法沒有修正項，是T的特征向量，網(wǎng)頁排名的過程等同于求解主特征向量的過程。不難看出，式(1)是一個迭代算法，其時間復(fù)雜度為(||2)。在實際應(yīng)用中，為了保證算法的收斂性，可令=，是元素全為1的向量，是調(diào)節(jié)因子。

3 算法并行化實現(xiàn)

大數(shù)據(jù)處理框架為處理和分析在線社交網(wǎng)絡(luò)大規(guī)模數(shù)據(jù)提供了技術(shù)支持，研究人員可以將已有的在線社交網(wǎng)絡(luò)個體影響力算法與具體的大數(shù)據(jù)并行計算框架相結(jié)合，用于分析用戶的影響力?？梢钥闯觯鲜鯬ageRank算法及其改進(jìn)算法的時間復(fù)雜度依然是(||2)。針對在線社交網(wǎng)絡(luò)用戶及其關(guān)系構(gòu)成的海量數(shù)據(jù)時，傳統(tǒng)的單機串行算法使內(nèi)存、CPU、I/O 等硬件資源無法滿足需要。通過MapReduce 和Spark兩種并行計算框架對改進(jìn)的PageRank 算法實現(xiàn)并行化編程，提高算法的執(zhí)行效率。

3.1 基于MapReduce并行框架

MapReduce是由Google公司提出的一種面向大規(guī)模數(shù)據(jù)處理的并行計算框架。它被分為map處理階段和reduce處理階段，并且每個階段的輸入和輸出都可以自定義數(shù)據(jù)類型的鍵值對格式。實際應(yīng)用中，開發(fā)人員需要指定map函數(shù)和reduce函數(shù)來實現(xiàn)相應(yīng)算法的不同功能，而不需要關(guān)注分布式底層實現(xiàn)機制。MapReduce程序執(zhí)行時，每個map操作都是并行運行且相互獨立的，但可能會受到數(shù)據(jù)源和CPU等硬件資源的影響。同樣地，多個reduce操作執(zhí)行時，所有具有相同鍵值的map輸出會聚集到同一個reduce中。在執(zhí)行map操作之前，大數(shù)據(jù)將會被分割成若干小數(shù)據(jù)塊，通過map函數(shù)處理完后會產(chǎn)生一系列鍵值對。這些鍵值對按鍵值進(jìn)行排序和合并，接著把整理好的數(shù)據(jù)輸入到多個reduce中，每個reduce操作對已經(jīng)排好序的并且?guī)в邢嗤I值的輸入數(shù)據(jù)進(jìn)行迭代計算，最后把結(jié)果輸出到HDFS中。MapReduce并行框架的另一個特點是并行處理時可以提供部分容錯和出錯恢復(fù)的功能，如當(dāng)一個map操作或reduce操作失效時，作業(yè)會被重新安排，從而保證作業(yè)連續(xù)執(zhí)行。

本文基于MapReduce計算框架對式(1)實現(xiàn)了并行化編程，主要是重寫map函數(shù)和reduce函數(shù)，偽代碼如算法1所示。顯然，該并行算法是迭代算法，當(dāng)不滿足迭代終止條件時，算法每一次的迭代操作都相同：map操作負(fù)責(zé)將每個用戶的影響力按權(quán)重比傳播給其他相關(guān)用戶，而reduce操作負(fù)責(zé)搜集各影響力分量并根據(jù)式(1)更新當(dāng)前用戶的影響力值。

算法1 基于MapReduce的個體影響力度量算法

輸入 帶權(quán)重的在線社交網(wǎng)絡(luò)結(jié)構(gòu)圖= {,,}，正則化因子

輸出 在線社交網(wǎng)絡(luò)用戶的社交影響力值

1) 計算轉(zhuǎn)移概率矩陣= {m}；

3) repeat：

4) map：

5) for each?do

6) for each(,)?do

7) 計算影響力傳播分量P?=m′()；

8) end

9) end

10) reduce：

11) for each?do

12)() = 0；

13) for each (,)?do

14) 影響力分量線性加權(quán)'()=()+P?；

15) end

17) end

18) untilconvergence；

19) for each?do

20) 輸出已收斂的用戶影響力值()；

21) end

3.2 基于Spark并行框架

Spark是由加州大學(xué)伯克利分校AMP實驗室開發(fā)的通用內(nèi)存并行計算框架。它的主要思想是通過一種新的作業(yè)和數(shù)據(jù)容錯方式來減少磁盤和網(wǎng)絡(luò)的I/O，從而提高海量數(shù)據(jù)的處理效率。彈性分布式數(shù)據(jù)集RDD是Spark的核心技術(shù)，表示已被分片、不可變地被并行操作的數(shù)據(jù)集合。RDD是對計算和數(shù)據(jù)的抽象，擁有方便重建的容錯機制并提供了轉(zhuǎn)換和動作兩大類算子。轉(zhuǎn)換算子負(fù)責(zé)將一個或多個RDD轉(zhuǎn)換成新的RDD，動作算子則根據(jù)生成的RDD產(chǎn)生最終的計算結(jié)果。Spark應(yīng)用提交后，外部數(shù)據(jù)經(jīng)過一系列轉(zhuǎn)換算子形成RDD；動作算子觸發(fā)作業(yè)提交，根據(jù)RDD之間的依賴關(guān)系創(chuàng)建有關(guān)所有操作的有向無環(huán)圖DAG計算模型；DAGScheduler解析DAG圖并將構(gòu)建不同的Stage，由任務(wù)調(diào)度器將Stage分解的任務(wù)集提交到集群節(jié)點中運行。

基于內(nèi)存計算的Spark并行框架適用于迭代算法，它的運行模式有多種，不同運行模式具有相似的運行流程，只是資源分配模式和任務(wù)調(diào)度模塊有所不同。本文結(jié)合Spark并行計算框架并行化實現(xiàn)了式(1)，并在Yarn運行模式進(jìn)行測試，偽代碼如算法2所示。類似于算法1，算法2也是迭代算法，每一次迭代的操作都相同：將在線社交網(wǎng)絡(luò)圖結(jié)構(gòu)等數(shù)據(jù)轉(zhuǎn)化成RDD格式數(shù)據(jù)集，flatmap()算子負(fù)責(zé)擴(kuò)散用戶的影響力，reducebykey()算子累加各影響力分量，map()算子依照式(1)更新當(dāng)前用戶的影響力值。

算法2 基于Spark的個體影響力度量算法

輸入 帶權(quán)重的在線社交網(wǎng)絡(luò)結(jié)構(gòu)圖{,,}，正則化因子

輸出 在線社交網(wǎng)絡(luò)用戶的社交影響力值

1) 計算轉(zhuǎn)移概率矩陣= {m}；

3) RDD (,,):= SparkContext (,). SparkOperator；

4) repeat：

5) for each?do

6) for each (,)?do

7) 計算影響力傳播分量RDD(,P?): RDD(,,). flatmap(lamda:P?=m′())；

9) end

10) end

11) untilconvergence；

12) for each?do

13) 輸出已收斂的用戶影響力值()；

14) end

4 實驗結(jié)果與分析

為了測試大數(shù)據(jù)處理框架對在線社交網(wǎng)絡(luò)個體影響力度量算法性能的影響，本文通過編程實現(xiàn)了上述兩種并行算法，并在真實大規(guī)模數(shù)據(jù)集上對比分析了算法的相關(guān)性能。

4.1 實驗數(shù)據(jù)及預(yù)處理

實驗數(shù)據(jù)集是通過湖南蟻坊軟件股份有限公司的爬蟲系統(tǒng)獲取的，主要利用新浪微博API接口搜集了新浪微博平臺注冊用戶在2016年11月2日至2017年6月26日期間產(chǎn)生的真實博文數(shù)據(jù)。每條博文數(shù)據(jù)是一個文本記錄，包括5個字段：時間戳、用戶ID、博文ID、轉(zhuǎn)發(fā)用戶ID、轉(zhuǎn)發(fā)博文ID。當(dāng)用戶發(fā)布某條原創(chuàng)博文時，該博文數(shù)據(jù)的轉(zhuǎn)發(fā)用戶ID和轉(zhuǎn)發(fā)博文ID字段就都為null。該數(shù)據(jù)集共涉及在線社交網(wǎng)絡(luò)平臺116 147 966位用戶產(chǎn)生的4 586 584 659條博文，其中，原創(chuàng)博文1 079 801 756條，轉(zhuǎn)發(fā)博文3 506 782 903條，具體統(tǒng)計信息如表1所示。

表1 實驗數(shù)據(jù)集統(tǒng)計信息

可以看出，不足10%的原創(chuàng)博文被其他用戶轉(zhuǎn)發(fā)，且只有約0.2%的原創(chuàng)博文被轉(zhuǎn)發(fā)超過500次，這說明在線社交網(wǎng)絡(luò)中少量用戶產(chǎn)生并控制著大量信息的傳播。圖1展示了上述數(shù)據(jù)集中原創(chuàng)博文被轉(zhuǎn)發(fā)次數(shù)的概率分布。該分布具有明顯的無標(biāo)度特性，符合指數(shù)為2.13的冪律分布，即少量原創(chuàng)博文存在較多的轉(zhuǎn)發(fā)次數(shù)。

圖1 原創(chuàng)博文轉(zhuǎn)發(fā)次數(shù)概率分布

個體影響力度量需要以特定的網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)進(jìn)行計算，本文通過提取上述數(shù)據(jù)集中用戶之間的轉(zhuǎn)發(fā)關(guān)系來構(gòu)建帶權(quán)重的在線社交網(wǎng)絡(luò)結(jié)構(gòu)圖。具體操作如下：首先，針對任何一條博文數(shù)據(jù)，抽取用戶ID和轉(zhuǎn)發(fā)用戶ID兩個字段數(shù)據(jù)；然后，刪除其中轉(zhuǎn)發(fā)用戶ID為null的轉(zhuǎn)發(fā)關(guān)系數(shù)據(jù)；最后，合并具有相同轉(zhuǎn)發(fā)關(guān)系的數(shù)據(jù)，得到具有轉(zhuǎn)發(fā)頻次的三元組轉(zhuǎn)發(fā)關(guān)系數(shù)據(jù)集，即<用戶ID, 轉(zhuǎn)發(fā)用戶ID, 頻次>。為了保護(hù)新浪微博用戶的隱私，需要對用戶ID進(jìn)行去隱私化處理，最終得到約59 GB的轉(zhuǎn)發(fā)關(guān)系數(shù)據(jù)集。若在數(shù)據(jù)集中存在三元組<,,f>，則表示用戶在樣本數(shù)據(jù)集中轉(zhuǎn)發(fā)用戶的相關(guān)博文共計f次。數(shù)據(jù)集共包含3 504 379 868個轉(zhuǎn)發(fā)關(guān)系三元組，涉及115 205 577位用戶，存儲在塊大小為128 MB的HDFS文件系統(tǒng)中。

基于轉(zhuǎn)發(fā)關(guān)系數(shù)據(jù)集，可以構(gòu)建在線社交網(wǎng)絡(luò)轉(zhuǎn)發(fā)關(guān)系結(jié)構(gòu)圖= {,,}。其中，表示用戶集合，表示用戶之間轉(zhuǎn)發(fā)關(guān)系構(gòu)成的邊集合，代表相應(yīng)的邊權(quán)重矩陣。在本實驗中，|| = 115 205 577，|| = 3 504 379 868。針對數(shù)據(jù)集中的任意三元組<,,f>，存在(,)?，且w,u=f。

圖2左邊是由用戶轉(zhuǎn)發(fā)關(guān)系三元組數(shù)據(jù)子集構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)圖示例，節(jié)點代表不同的用戶，邊的方向代表了博文轉(zhuǎn)發(fā)路徑，邊的權(quán)值代表用戶之間的轉(zhuǎn)發(fā)頻次。如用戶2共w1,u2=4次轉(zhuǎn)發(fā)過用戶1的博文。在線社交網(wǎng)絡(luò)用戶的個體影響力以博文信息為載體，沿著轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)進(jìn)行擴(kuò)散。因此，個體影響力的擴(kuò)散路徑和概率可以由帶權(quán)重的用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)圖計算得到，即對任意的邊(,)?，存在從用戶到用戶影響力擴(kuò)散路徑，且擴(kuò)散概率為

圖2右邊所示是基于在線社交網(wǎng)絡(luò)用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)圖計算影響力擴(kuò)散概率的示例，虛線表示影響力擴(kuò)散路徑，邊上的概率值是對應(yīng)的影響力擴(kuò)散概率。實際應(yīng)用中，通過式(2)可以計算出算法1和算法2中所需的轉(zhuǎn)移概率矩陣。

4.2 實驗環(huán)境

本實驗中，算法1和算法2兩種并行算法及對數(shù)據(jù)的預(yù)處理都是通過Java語言編程實現(xiàn)，使用的開發(fā)工具包是JDK1.8。實現(xiàn)的并行算法程序運行在由騰訊云服務(wù)器搭建的Hadoop分布式集群環(huán)境中，Hadoop版本為2.7.4，Spark版本為1.6.2。該集群共由128個獨立的內(nèi)存型M2服務(wù)器節(jié)點組成，每個節(jié)點的硬件配置如下：8核CPU，64 GB內(nèi)存，500 GB硬盤，1 Mbit/s帶寬，預(yù)裝系統(tǒng)版本為Ubuntu Server 14.04.1 LTS 64位。為了對比算法在不在規(guī)模集群上的性能，本實驗分別搭建了6種不同規(guī)模的集群環(huán)境，其唯一區(qū)別是具有不同的服務(wù)器節(jié)點數(shù)目，分別是4、8、16、32、64、128。在不同集群環(huán)境中，其中，只有一臺服務(wù)器作為主節(jié)點，其他服務(wù)器均是數(shù)據(jù)節(jié)點或計算節(jié)點。本文實現(xiàn)并在單機環(huán)境下運行了在線社交網(wǎng)絡(luò)個體影響力測試算法，其使用的機器也是騰訊云提供的內(nèi)存型M2服務(wù)器。

圖2 影響力擴(kuò)散示例

4.3 性能指標(biāo)與測試參數(shù)

針對在線社交網(wǎng)絡(luò)個體影響力度量算法，本實驗主要從準(zhǔn)確度和運行時間等指標(biāo)對基于式(1)的并行化算法1和算法2在真實數(shù)據(jù)上進(jìn)行相關(guān)性能測試。

準(zhǔn)確度方面。由于缺少針對大規(guī)模用戶影響力值計算的標(biāo)準(zhǔn)測試數(shù)據(jù)集，本實驗主要從算法收斂情況對準(zhǔn)確度進(jìn)行測試。式(1)本質(zhì)上是冪迭代算法，因此算法1和算法2在實際運行過程中需要預(yù)先設(shè)置終止條件。當(dāng)程序運行達(dá)到終止條件時，算法迭代結(jié)束，實驗將會記錄此時的迭代次數(shù)和迭代條件變化情況，具體地給定第次迭代后計算的用戶影響力值向量，當(dāng)式(3)成立時，程序終止，算法收斂。

其中，表示實驗數(shù)據(jù)集中的用戶數(shù)，誤差限=10?8。||×||1表示向量的1?范數(shù)，即向量所有元素的絕對值之和。當(dāng)= 0時，0表示初始化的用戶影響力值。式(3)認(rèn)為平均每個用戶的影響力數(shù)值誤差不超過10?8時，計算結(jié)果趨于穩(wěn)定，算法已收斂。

運行時間方面。通過設(shè)置不同參數(shù)，實驗將記錄算法在不同數(shù)據(jù)集以及不同分布式集群上的運行時間和加速比?；谑?1)的在線社交網(wǎng)絡(luò)個體影響力度量算法只需設(shè)置一個參數(shù)，它是正則化因子，也稱為跳轉(zhuǎn)因子。在進(jìn)行大規(guī)模網(wǎng)頁排名計算時，通常取值為0.85，表示上網(wǎng)者按照鏈接瀏覽網(wǎng)頁的概率為0.85，隨機跳轉(zhuǎn)到一個新網(wǎng)頁的概率為0.15。在線社交網(wǎng)絡(luò)用戶的轉(zhuǎn)發(fā)行為不同于上網(wǎng)者隨機點擊頁面的過程，因此本實驗測試了并行算法在a值分別為0.5、0.7、0.85和0.95時的性能。

并行化算法在不同數(shù)據(jù)集上的性能存在差異，為了探究大數(shù)據(jù)處理框架在不同數(shù)據(jù)集上的加速效果，本實驗基于數(shù)據(jù)集劃分了不同規(guī)模的數(shù)據(jù)子集D1、D2、D3、D4、D5，具體描述如表2所示。這些數(shù)據(jù)集涉及的在線社交網(wǎng)絡(luò)用戶規(guī)模從十萬級至億級遞增，用戶之間形成的轉(zhuǎn)發(fā)關(guān)系數(shù)也相應(yīng)增加，最多達(dá)到十億級規(guī)模。

表2 實驗數(shù)據(jù)集子集描述

在線社交網(wǎng)絡(luò)密度用于刻畫中節(jié)點間連邊的密集程度，定義為圖= {,,}的鄰接矩陣中非零元素所占比例，在此又稱稠密度。具有相同用戶數(shù)的在線社交網(wǎng)絡(luò)數(shù)據(jù)集，拓?fù)鋱D的稠密度也會由于用戶之間轉(zhuǎn)發(fā)關(guān)系數(shù)的不同而有所差異。本實驗以數(shù)據(jù)子集D1為樣本，通過隨機采樣增加或減少節(jié)點間邊的方法構(gòu)造了具有不同稠密度的數(shù)據(jù)子集D1_A、D1_B、D2_A、D2_B、D2_C，如表2所示。通過對上述數(shù)據(jù)子集進(jìn)行實驗，可以探究稠密度對算法性能的影響。

4.4 結(jié)果與分析

本文依照上節(jié)中指標(biāo)要求和參數(shù)設(shè)置，在不同真實數(shù)據(jù)子集上對在線社交網(wǎng)絡(luò)個體影響力并行化算法1和算法2進(jìn)行了相關(guān)性能測試。由于目前不存在針對在線社交網(wǎng)絡(luò)用戶影響力計算的標(biāo)準(zhǔn)測試數(shù)據(jù)，所以從收斂性和計算效率兩方面對本實驗結(jié)果進(jìn)行分析，具體實驗結(jié)果及其對比情況如下所述。

4.4.1 收斂性分析

由于算法1和算法2都是基于式(1)的并行化實現(xiàn)，因此在不同的大數(shù)據(jù)處理框架下算法具有相同的收斂情況。本節(jié)將以基于Spark的并行化算法2為例，在不同參數(shù)配置環(huán)境中闡述算法在不同數(shù)據(jù)子集上的收斂性能，基于MapReduce的并行化算法1的情況類似。

實驗結(jié)果表明，給定值，同一數(shù)據(jù)子集在不同規(guī)模集群上的收斂情況相同，數(shù)據(jù)子集D1、D2、D3、D4、D5第一次滿足收斂條件（=10?8）時，算法的迭代次數(shù)分別是83、84、84、84、85。這是因為集群規(guī)模的變化只會引發(fā)計算資源的變化，不會改變算法的運行原理。圖3是在16節(jié)點集群下，=0.85時算法2在不同數(shù)據(jù)子集中的收斂趨勢變化。在迭代初期，收斂速度較快，隨著程序運行，收斂速度逐漸變慢。當(dāng)收斂條件相同時，基于式(1)的在線社交網(wǎng)絡(luò)個體影響力度量算法的收斂速度與用戶規(guī)模無關(guān)。

圖3 算法1在不同數(shù)據(jù)子集中的收斂變化情況

在64節(jié)點集群上，基于不同值的算法2在數(shù)據(jù)子集D4上的收斂變化情況如圖4所示。可以看出，隨著a值的增加，算法2的收斂速度變慢。當(dāng)取值依次為0.5、0.7、0.85時，算法2收斂所需迭代次數(shù)分別是25、44、84。當(dāng)=0.95時，算法2迭代第212次時的收斂誤差為2.2×10?8，此時仍未滿足收斂條件。由此可見，在線社交網(wǎng)絡(luò)用戶傾向于轉(zhuǎn)發(fā)好友的博文時，取值偏高，個體影響力度量算法的收斂速度越慢。在實際應(yīng)用中，算法應(yīng)根據(jù)具體的在線社交網(wǎng)絡(luò)平臺用戶行為特征，設(shè)置合理的跳轉(zhuǎn)因子參數(shù)進(jìn)行計算。

圖4 算法2在不同a值時的收斂變化情況

基于不同稠密度的數(shù)據(jù)子集D1、D1_A、D1_B，在8節(jié)點集群上，圖5展示了算法2在=0.85時收斂情況。當(dāng)滿足收斂條件（=10?8）時，算法的迭代次數(shù)分別為83、79、70。這說明在線社交網(wǎng)絡(luò)個體影響力度量算法的收斂速度與用戶之間關(guān)系構(gòu)成的圖稠密度有關(guān)，通過構(gòu)建具有不同稠密度的概率轉(zhuǎn)移矩陣，基于式(1)的個體影響力計算方法的收斂性能會有所差異。

圖5 算法2在不同稠密度數(shù)據(jù)子集中的收斂變化情況

4.4.2 效率分析

大數(shù)據(jù)處理框架的特點是可以提高算法處理數(shù)據(jù)的能力，基于大數(shù)據(jù)處理框架的并行化算法在不同參數(shù)配置環(huán)境下具有不同的計算效率。由于在擁有少量服務(wù)器節(jié)點的集群環(huán)境中，處理大規(guī)模數(shù)據(jù)集所需時間較長，因此在進(jìn)行效率分析時，算法的終止條件是迭代達(dá)到預(yù)設(shè)次數(shù)，而不是收斂誤差小于預(yù)設(shè)閾值。接下來，本文將從多個角度對比分析基于Spark和MapReduce框架并行化程序的運行效率。

一般采用加速比衡量并行化程序的性能和效果，它是指同一個任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運行消耗時間的比率。圖6顯示了當(dāng)=0.85時，算法1和算法2在具有不同服務(wù)器節(jié)點數(shù)目集群中的加速比情況，其中，程序在數(shù)據(jù)子集D1、D2、D3、D4、D5中的運行迭代次數(shù)分別設(shè)置為50、40、30、20、20?？傮w而言，在相同情況下，基于Spark框架的并行化算法的加速比要高于基于MapReduce框架的并行化算法。這是因為Spark是基于內(nèi)存進(jìn)行的迭代計算，其帶來的性能提升更大。當(dāng)然，集群中服務(wù)器節(jié)點數(shù)目的增多對于兩種并行化算法都具有一定的加速作用，且在大規(guī)模數(shù)據(jù)子集上效果更明顯。這是因為隨著服務(wù)器節(jié)點數(shù)目增多，可用的計算資源越多，算法運行效率越高；隨著數(shù)據(jù)子集規(guī)模增大，計算資源利用更充分，帶來的加速效果更明顯。

但在有些情形下，當(dāng)集群節(jié)點數(shù)目繼續(xù)增多時，并行化算法的加速比反而減小。如圖6(b)所示，算法2在每個數(shù)據(jù)子集中都有一個最高加速比，其對應(yīng)的集群節(jié)點數(shù)目分別是8、32、32、64、64。這些集群節(jié)點數(shù)目又稱為算法在該數(shù)據(jù)子集下加速比曲線的性能拐點。當(dāng)集群中節(jié)點數(shù)目超過其拐點時，由于并行化模型的限制和大數(shù)據(jù)處理框架的特征，算法的加速性能不會隨著集群節(jié)點的增多而繼續(xù)提高。圖6(a)展示了算法1在數(shù)據(jù)子集D1、D2中的性能拐點分別是8、32，而在其他數(shù)據(jù)子集中并未出現(xiàn)性能拐點。這說明通過增加集群中服務(wù)器節(jié)點數(shù)量，算法1在數(shù)據(jù)子集D3、D4、D5中獲得的加速比會持續(xù)增大。此外，算法1在數(shù)據(jù)子集D1中的加速比均小于1。由于該數(shù)據(jù)子集規(guī)模小，分布式環(huán)境中服務(wù)器節(jié)點間的通信、子任務(wù)的創(chuàng)建、數(shù)據(jù)塊分發(fā)等消耗的時間大于算法1相較于串行算法節(jié)省的運行時間。

圖6 不同規(guī)模集群環(huán)境中算法的加速比

在128服務(wù)器節(jié)點集群環(huán)境中，當(dāng)收斂條件都滿足式(3)且=10?8、=0.85時，圖7顯示了算法1和算法2在不同規(guī)模數(shù)據(jù)子集中的運行時間。

圖7 算法在不同規(guī)模數(shù)據(jù)子集中的運行時間

顯然，隨著數(shù)據(jù)集規(guī)模的增長，算法1和算法2的運行時間都呈現(xiàn)遞增趨勢，且在不同數(shù)據(jù)子集中，算法2的執(zhí)行時間顯著少于算法1的執(zhí)行時間。此外，結(jié)合上述分析，當(dāng)性能拐點出現(xiàn)后，兩種并行化算法的運行時間之差逐漸縮小。

以數(shù)據(jù)子集D3為例，圖8所示是算法1和算法2在不同規(guī)模集群環(huán)境中迭代運行30次的單次平均迭代時間及其方差，此時= 0.85。可以看出，隨著集群節(jié)點數(shù)目的增多，算法單次迭代所需時間更少，這與圖6中結(jié)果一致。當(dāng)算法2出現(xiàn)性能拐點（集群節(jié)點數(shù)目32）后，其單次迭代時間開始增長。算法1單次迭代時間的方差要大于算法2，這說明該實驗中Spark并行框架的計算效率更穩(wěn)定。

圖8 不同規(guī)模集群環(huán)境中算法迭代一次的時間

在具有64節(jié)點服務(wù)器的集群環(huán)境中，圖9展示了當(dāng)取不同值時，兩種并行化算法在數(shù)據(jù)子集D4上迭代計算20次的單次平均迭代時間及其方差?？梢钥闯?，算法1完成一次迭代計算所需時間更長。當(dāng)=0.95時，算法1和算法2的單次迭代所需時間最長，而當(dāng)=0.85時，算法1和算法2的單次迭代所需時間最短。這說明值的選取對基于式(1)的在線社交網(wǎng)絡(luò)個體影響力度量算法的計算效率具有直接影響。

圖10是在16節(jié)點集群環(huán)境中，算法1和算法2針對具有相同規(guī)模不同稠密度的數(shù)據(jù)子集D2、D2_A、D2_B、D2_C，迭代運行40次的單次平均迭代時間及其方差，此時，=0.85。不難看出，隨著相同規(guī)模數(shù)據(jù)子集稠密度的增加，算法1和算法2完成單次迭代所需時間更長，且它們的方差也在變大。這說明在計算在線社交網(wǎng)絡(luò)用戶的個體影響力時，不僅用戶數(shù)規(guī)模會直接影響算法的效率，而且用戶間關(guān)系構(gòu)建的網(wǎng)絡(luò)圖密度也會影響算法的計算效率。

圖9 不同a值時算法迭代一次的時間

圖10 算法在不同稠密度數(shù)據(jù)子集中迭代一次的時間

5 結(jié)束語

本文主要基于一種經(jīng)典的在線社交網(wǎng)絡(luò)個體影響力算法，結(jié)合MapReduce和Spark兩種并行計算框架，在真實大規(guī)模新浪微博數(shù)據(jù)集上進(jìn)行了性能測試。實驗結(jié)果表明，大數(shù)據(jù)處理框架能夠?qū)υ诰€社交網(wǎng)絡(luò)個體影響力算法的效率產(chǎn)生顯著影響。MapReduce和Spark由于內(nèi)在并行機制的差異，導(dǎo)致算法處理大數(shù)據(jù)集時的性能也會存在差別。在實際使用過程中，多種參數(shù)的設(shè)置和實驗數(shù)據(jù)集的特征對算法的收斂性和計算效率有直接影響。由于數(shù)據(jù)集規(guī)模的不同，大數(shù)據(jù)處理框架對算法在集群計算過程中帶來的加速性能不同。在線社交網(wǎng)絡(luò)用戶之間關(guān)系構(gòu)建的圖結(jié)構(gòu)越稠密，其計算復(fù)雜度越高，算法迭代次數(shù)和運行時間會更多。

本文只對個體影響力度量算法進(jìn)行了簡單的并行化實現(xiàn)，在實驗過程中大數(shù)據(jù)處理框架相關(guān)參數(shù)采用默認(rèn)配置，主要是為了測試文中算法在大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)中的性能，以及對后續(xù)個體影響力算法的設(shè)計和并行化實現(xiàn)提供實證參考依據(jù)。因此，進(jìn)一步工作可以通過優(yōu)化大數(shù)據(jù)處理框架的相關(guān)參數(shù)提高在線社交網(wǎng)絡(luò)個體影響力并行化算法的性能。

[1] 方濱興, 許進(jìn), 李建華. 在線社交網(wǎng)絡(luò)分析[M]. 北京: 電子工業(yè)出版社, 2014.

FANG B X, XU J, LI J H. Online social network analysis[M]. Beijing: Publishing House of Electronics Industry, 2014.

[2] CIALDINI R B. Influence: science and practice[M]. Boston: Allyn and Bacon, 2003.

[3] 吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析[J]. 計算機學(xué)報, 2014, 37(4):735-752.

WU X D, LI Y, LI L. Influence analysis of online social networks[J]. Chinese Journal of Computers, 2014, 37(4):735-752.

[4] TING I H, CHANGP S, WANG S L. Understanding microblog users for social recommendation based on social networks analysis[J]. Journal of Universal Computer Science, 2012, 18(4):554-576.

[5] LI N, GILLET D. Identifying influential scholars in academic social media platforms[C]//The 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2013: 608-614.

[6] VEGA-OLIVEROS D A, BERTON L, LOPES A D A, et al. Influence maximization based on the least in-fluential spreaders[C]//The 1st International Conference on Social Influence Analysis. 2015: 3-8.

[7] DINH T N, ZHANG H, NGUYEN D T, et al. Cost-effective viral marketing for time-critical campaigns in large-scale social networks[J]. IEEE/ACM Transactions on Networking, 2014, 22(6):2001-2011.

[8] KATZ E, LAZARSFELD P. Personal influence: the part played by people in the flow of mass communica-tions[M]. New Jersey: Transaction Publishers, 1966.

[9] CHA M, HADDADI H, BENEVENUTO F, et al. Measuring user influence in twitter: the million follower fallacy[C]//International Conference on Weblogs and Social Media.2010: 10-17.

[10] DING Z, JIA Y, ZHOU B, et al. Mining topical influencers based on the multi-relational network in microblogging sites[J]. China Communications, 2013, 10(1):93-104.

[11] WENG J, LIM E P, JIANG J, et al. TwitterRank: finding topic-sensitive influential twitterers[C]//The third ACM International Conference on Web Search and Data Mining. 2010: 261-270.

[12] TANG J, SUN J, WANG C,et al. Social influence anal-ysis in large-scale networks[C]//The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009: 807-816.

[13] LIU X, LI M, LI S, et al. IMGPU: GPU-accelerated influence maximization in large-scale social networks[J]. IEEE Transactions on Parallel and distributed Systems, 2014, 25(1):136-145.

[14] 平宇, 向陽, 張波, 等. 基于MapReduce的并行PageRank算法實現(xiàn)[J]. 計算機工程, 2014, 40(2):31-34.

PING Y, XIANG Y, ZHANG B, et al. Implementation of parallel PageRank algorithm[J]. Computer Engineering Based on MapReduce, 2014, 40(2):31-34.

[15] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3):215-239.

[16] NEWMAN M E J. A measure of betweenness centrality based on random walks[J]. Social Networks, 2005, 27(1):39-54.

[17] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2):167-256.

[18] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.

[19] PAGE L, BRIN S, MOTWANI R, et al. The pagerank citation ranking: bringing order to the web[J]. Stanford Digital Libraries Working Paper, 1998, 9(1):1-14.

[20] EFRON M. Information search and retrieval in microblogs[J]. Journal of the American Society for Information Science and Technology, 2011, 62(6): 996-1008.

[21] HAVELIWALA T, KAMVAR A, JEH G. An analytical comparison of approaches to personalizing pagerank[R]. Palo Alto: Stanford University, 2003.

[22] SONG X, CHI Y, HINO K, et al. Identifying opinion leaders in the blogosphere[C]//The 6th ACM Conference on Information and Knowledge Management. 2007: 971-974.

Performance analysis and testing of personal influence algorithmin online social networks

QUAN Yong1, JIA Yan1, ZHANG Liang1, ZHU Zheng1, ZHOU Bin1, FANG Binxing2

1. College of Computer, National University of Defense Technology, Changsha 410073, China 2. College of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China

Social influence is the key factor to drive information propagation in online social networks and can be modeled and analyzed with social networking data. As a kind of classical personal influence algorithm, two parallel implementation versions of a PageRank based method were introduced. Furthermore, extensive experiments were conducted on a large-scale real dataset to test the performance of these parallel methods in a distributed environment. The results demonstrate that the computational efficiency of the personal influence algorithm can be improved significantly in massive data sets by virtue of existing big data processing framework, and provide an empirical reference for the future research and optimization of the algorithm as well.

performance testing, social influence, distributed computing, online social networks

TP391

A

10.11959/j.issn.1000?436x.2018217

全擁（1988?），男，湖南常德人，國防科技大學(xué)博士生，主要研究方向為在線社交網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘。

賈焰（1960?），女，四川成都人，博士，國防科技大學(xué)教授、博士生導(dǎo)師，主要研究方向為數(shù)據(jù)挖掘、大數(shù)據(jù)分析、信息安全等。

張良（1989?），男，江西九江人，國防科技大學(xué)博士生，主要研究方向為在線社交網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘。

朱爭（1993?），男，四川攀枝花人，國防科技大學(xué)碩士生，主要研究方向為信息安全。

周斌（1971?），男，江西吉安人，博士，國防科技大學(xué)研究員、博士生導(dǎo)師，主要研究方向為數(shù)據(jù)挖掘、信息安全。

方濱興（1960?），男，江西上饒人，博士，中國工程院院士，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)、信息安全、并行計算等。

2017?11?21；

2018?08?22

全擁，qy8801@nudt.edu.cn

國家重點研發(fā)計劃基金資助項目（No.2017YFB0803303）；國家自然科學(xué)基金資助項目（No.61502517）；湖南省重點研發(fā)計劃資助項目（No.2018GK2056）

The National Key Research and Development Program of China (No.2017YFB0803303),The National Natural Science Foundation of China (No.61502517), The Key Research and Development Project of Hunan Province (No.2018GK2056)