在線社交網絡個體影響力算法測試與性能評估

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

?

在線社交網絡個體影響力算法測試與性能評估

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

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

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

性能測試；社交影響力；分布式計算；在線社交網絡

1 引言

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

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

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

2 個體影響力計算方法

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

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

=MT+(1)

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

3 算法并行化實現

大數據處理框架為處理和分析在線社交網絡大規模數據提供了技術支持，研究人員可以將已有的在線社交網絡個體影響力算法與具體的大數據并行計算框架相結合，用于分析用戶的影響力。可以看出，上述PageRank算法及其改進算法的時間復雜度依然是(||2)。針對在線社交網絡用戶及其關系構成的海量數據時，傳統的單機串行算法使內存、CPU、I/O 等硬件資源無法滿足需要。通過MapReduce 和Spark兩種并行計算框架對改進的PageRank 算法實現并行化編程，提高算法的執行效率。

3.1 基于MapReduce并行框架

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

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

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

輸入 帶權重的在線社交網絡結構圖= {,,}，正則化因子

輸出 在線社交網絡用戶的社交影響力值

1) 計算轉移概率矩陣= {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) 影響力分量線性加權'()=()+P?；

15) end

17) end

18) untilconvergence；

19) for each?do

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

21) end

3.2 基于Spark并行框架

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

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

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

輸入 帶權重的在線社交網絡結構圖{,,}，正則化因子

輸出 在線社交網絡用戶的社交影響力值

1) 計算轉移概率矩陣= {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 實驗結果與分析

為了測試大數據處理框架對在線社交網絡個體影響力度量算法性能的影響，本文通過編程實現了上述兩種并行算法，并在真實大規模數據集上對比分析了算法的相關性能。

4.1 實驗數據及預處理

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

表1 實驗數據集統計信息

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

圖1 原創博文轉發次數概率分布

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

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

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

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

4.2 實驗環境

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

圖2 影響力擴散示例

4.3 性能指標與測試參數

針對在線社交網絡個體影響力度量算法，本實驗主要從準確度和運行時間等指標對基于式(1)的并行化算法1和算法2在真實數據上進行相關性能測試。

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

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

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

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

表2 實驗數據集子集描述

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

4.4 結果與分析

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

4.4.1 收斂性分析

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

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

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

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

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

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

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

4.4.2 效率分析

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

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

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

圖6 不同規模集群環境中算法的加速比

在128服務器節點集群環境中，當收斂條件都滿足式(3)且=10?8、=0.85時，圖7顯示了算法1和算法2在不同規模數據子集中的運行時間。

圖7 算法在不同規模數據子集中的運行時間

顯然，隨著數據集規模的增長，算法1和算法2的運行時間都呈現遞增趨勢，且在不同數據子集中，算法2的執行時間顯著少于算法1的執行時間。此外，結合上述分析，當性能拐點出現后，兩種并行化算法的運行時間之差逐漸縮小。

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

圖8 不同規模集群環境中算法迭代一次的時間

在具有64節點服務器的集群環境中，圖9展示了當取不同值時，兩種并行化算法在數據子集D4上迭代計算20次的單次平均迭代時間及其方差。可以看出，算法1完成一次迭代計算所需時間更長。當=0.95時，算法1和算法2的單次迭代所需時間最長，而當=0.85時，算法1和算法2的單次迭代所需時間最短。這說明值的選取對基于式(1)的在線社交網絡個體影響力度量算法的計算效率具有直接影響。

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

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

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

5 結束語

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

本文只對個體影響力度量算法進行了簡單的并行化實現，在實驗過程中大數據處理框架相關參數采用默認配置，主要是為了測試文中算法在大規模社交網絡數據中的性能，以及對后續個體影響力算法的設計和并行化實現提供實證參考依據。因此，進一步工作可以通過優化大數據處理框架的相關參數提高在線社交網絡個體影響力并行化算法的性能。

[1] 方濱興, 許進, 李建華. 在線社交網絡分析[M]. 北京: 電子工業出版社, 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] 吳信東, 李毅, 李磊. 在線社交網絡影響力分析[J]. 計算機學報, 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算法實現[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?），男，湖南常德人，國防科技大學博士生，主要研究方向為在線社交網絡分析、數據挖掘。

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

張良（1989?），男，江西九江人，國防科技大學博士生，主要研究方向為在線社交網絡分析、數據挖掘。

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

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

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

2017?11?21；

2018?08?22

全擁，qy8801@nudt.edu.cn

國家重點研發計劃基金資助項目（No.2017YFB0803303）；國家自然科學基金資助項目（No.61502517）；湖南省重點研發計劃資助項目（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)