基于Hadoop云平臺的新浪微博社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)挖掘算法

陳紅松 王 鋼 張 鵬

(1北京科技大學(xué)計(jì)算機(jī)與通信工程學(xué)院, 北京 100083)(2材料領(lǐng)域知識工程北京市重點(diǎn)實(shí)驗(yàn)室， 北京 100083)(3鐵道警察學(xué)院， 鄭州 450053)

微博社交網(wǎng)絡(luò)是一個(gè)不斷發(fā)展并對社會(huì)產(chǎn)生巨大影響的傳播平臺，對微博社會(huì)網(wǎng)絡(luò)中信息傳播過程中關(guān)鍵節(jié)點(diǎn)的分析挖掘研究具有重要的理論意義和應(yīng)用前景.作為一個(gè)新興的信息傳播平臺，微博社交網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)與傳播規(guī)律研究在理論及應(yīng)用方面都具有很高的價(jià)值，特別是在信息傳播模型、關(guān)鍵節(jié)點(diǎn)挖掘、用戶行為分析等方面[1].研究微博信息傳播中關(guān)鍵節(jié)點(diǎn)挖掘算法的目的在于發(fā)現(xiàn)信息傳播規(guī)律中的關(guān)鍵節(jié)點(diǎn)，以及關(guān)鍵節(jié)點(diǎn)對微博信息傳播的作用.近年來，國內(nèi)外已有許多算法用來對微博數(shù)據(jù)進(jìn)行分析挖掘，例如基于社交網(wǎng)絡(luò)特點(diǎn)對PageRank進(jìn)行加權(quán)改進(jìn)的研究[2]、基于隨機(jī)網(wǎng)絡(luò)的數(shù)據(jù)挖掘研究、啟發(fā)式社交網(wǎng)絡(luò)節(jié)點(diǎn)影響力計(jì)算方法[3]等.上述研究通過數(shù)據(jù)預(yù)處理和特征值競爭抑制機(jī)制較好地完成數(shù)據(jù)過濾，從而提高數(shù)據(jù)處理效率[4].這些研究的重點(diǎn)都是探索如何讓算法更高效地對數(shù)據(jù)進(jìn)行處理，提高算法的執(zhí)行效率，但存在未能體現(xiàn)社交網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)連接的社會(huì)屬性的缺陷.本文通過給社交網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊賦予適當(dāng)?shù)纳鐣?huì)屬性權(quán)重，體現(xiàn)出節(jié)點(diǎn)的社會(huì)屬性差異以及信息在社交網(wǎng)絡(luò)中傳播的特點(diǎn)和規(guī)律，從而在提高關(guān)鍵節(jié)點(diǎn)挖掘算法執(zhí)行效率的同時(shí)，發(fā)現(xiàn)符合社交網(wǎng)絡(luò)自身特點(diǎn)的關(guān)鍵節(jié)點(diǎn)及高價(jià)值分析結(jié)果.

本文首先針對熱點(diǎn)微博的信息轉(zhuǎn)發(fā)過程進(jìn)行數(shù)據(jù)采集，根據(jù)微博轉(zhuǎn)發(fā)過程構(gòu)建一個(gè)信息轉(zhuǎn)發(fā)傳播網(wǎng)絡(luò)，通過HITS算法挖掘信息傳播過程中起關(guān)鍵作用的節(jié)點(diǎn).本文的微博實(shí)驗(yàn)數(shù)據(jù)來自新浪微博API開放平臺，整個(gè)數(shù)據(jù)處理流程在Hadoop云平臺下進(jìn)行，在大規(guī)模社會(huì)網(wǎng)絡(luò)分析工具X-RIME開源框架基礎(chǔ)上，采用分布式HITS算法對微博信息傳播數(shù)據(jù)進(jìn)行分析，并針對社交網(wǎng)絡(luò)自身特點(diǎn)提出新的加權(quán)HITS算法用于挖掘關(guān)鍵節(jié)點(diǎn)，并通過實(shí)驗(yàn)進(jìn)行分析驗(yàn)證.

1 X-RIME開源框架

X-RIME是一個(gè)基于Hadoop的大規(guī)模社會(huì)網(wǎng)絡(luò)分析開源軟件[5]，在Map/Reduce框架上對十幾種社會(huì)網(wǎng)絡(luò)分析算法進(jìn)行并行化與分布式化處理，能夠?qū)Υ笠?guī)模社會(huì)網(wǎng)絡(luò)/復(fù)雜網(wǎng)絡(luò)進(jìn)行社會(huì)網(wǎng)絡(luò)分析，具有良好的擴(kuò)展性和通用性，研究人員可自由獲得X-RIME的程序包和源代碼.X-RIME算法庫實(shí)現(xiàn)了許多社會(huì)網(wǎng)絡(luò)分析常用算法，如最小生成樹算法、節(jié)點(diǎn)度統(tǒng)計(jì)、弱連通算法、強(qiáng)連通算法、PageRank算法、高質(zhì)量網(wǎng)頁分析算法HITS (hyperlink-induced topic search)等.這些算法都支持分布式并行計(jì)算.PageRank算法對網(wǎng)絡(luò)中所有節(jié)點(diǎn)給出全局重要性排序，有利于迅速響應(yīng)用戶主題檢索請求，缺點(diǎn)在于檢索主題的無關(guān)性.HITS算法是對網(wǎng)絡(luò)中與主題相關(guān)的子集進(jìn)行分析，它需要的迭代次數(shù)更少，收斂速度更快.本文研究的場景是社交網(wǎng)絡(luò)信息傳播過程中的關(guān)鍵節(jié)點(diǎn)挖掘，這些關(guān)鍵節(jié)點(diǎn)是與網(wǎng)絡(luò)傳播主題相關(guān)的網(wǎng)絡(luò)節(jié)點(diǎn)子集，因此本文以HITS算法作為研究對象.

2 基于Hadoop平臺的分布式HITS算法

在傳統(tǒng)的社會(huì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)分析中，節(jié)點(diǎn)中心度分析是較常用的方法，主要有點(diǎn)度中心度、加權(quán)點(diǎn)度中心度、中介中心度、接近中心度4種[6].但這幾種中心度都有其局限性，難以反映在線社交網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)屬性及特征.本文基于HITS算法來挖掘微博社會(huì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn).HITS算法基于節(jié)點(diǎn)之間的連接關(guān)系分析節(jié)點(diǎn)重要程度，通過計(jì)算節(jié)點(diǎn)的出入度及節(jié)點(diǎn)間連接關(guān)系分析挖掘社會(huì)網(wǎng)絡(luò)信息傳播過程中的關(guān)鍵節(jié)點(diǎn).

2.1 HITS算法思想

HITS算法是鏈接分析中一種基礎(chǔ)且重要的算法[7]，是IBM 公司阿爾馬登研究中心“CLEVER”研究項(xiàng)目中的一部分，目前已被Teoma搜索引擎(www.teoma.com)作為鏈接分析算法在實(shí)際中使用.HITS算法中有2個(gè)重要概念：權(quán)威值(authority)和中介值(hub).網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有權(quán)威值和中介值，權(quán)威值表示一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的權(quán)威性，中介值表示一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中傳播信息的能力，中介值越高，說明這個(gè)節(jié)點(diǎn)在信息傳播擴(kuò)散中起的作用就越大.HITS算法的核心思想是分析計(jì)算權(quán)威值和中介值在網(wǎng)絡(luò)系統(tǒng)中的相互作用、相互影響，可挖掘微博社會(huì)網(wǎng)絡(luò)中信息傳播過程中的關(guān)鍵節(jié)點(diǎn).

2.2 HITS算法步驟

HITS算法包括值分配(delivery)、匯總(summer)、規(guī)范化(normalize)3個(gè)運(yùn)算階段[8].第1階段是值分配階段，對節(jié)點(diǎn)的權(quán)威值和中介值進(jìn)行初始化和值分配.具體步驟如下：

① 為整個(gè)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都賦予一個(gè)初始的非負(fù)中介值和權(quán)威值.通常將中介值和權(quán)威值分別初始化為1.

② 進(jìn)行迭代運(yùn)算得到節(jié)點(diǎn)p的權(quán)威值和中介值，運(yùn)算公式為

(1)

(2)式中，n為指向p的某個(gè)節(jié)點(diǎn)；N為所有指向p的節(jié)點(diǎn)的集合；ap和hp分別為節(jié)點(diǎn)p的權(quán)威值和中介值.

式(1)表明，如果節(jié)點(diǎn)p被許多有較高中介值的節(jié)點(diǎn)所指，那么節(jié)點(diǎn)p的權(quán)威值會(huì)增加，而增加的值就是那些指向節(jié)點(diǎn)p的所有節(jié)點(diǎn)的中介值總和.式(2)表明，如果節(jié)點(diǎn)p指向許多權(quán)威值較高的節(jié)點(diǎn)，那么節(jié)點(diǎn)p的中介值會(huì)增加，而增加的值就是節(jié)點(diǎn)p指向的所有節(jié)點(diǎn)權(quán)威值的總和.經(jīng)過值分配階段后，由于多次迭代會(huì)導(dǎo)致結(jié)果數(shù)值增加速度過快，不利于算法的繼續(xù)運(yùn)行，因此要對數(shù)據(jù)進(jìn)行匯總和規(guī)范化處理.

在匯總階段，對整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的權(quán)威值和中介值進(jìn)行匯總，為下階段的數(shù)據(jù)規(guī)范化做準(zhǔn)備.

數(shù)據(jù)匯總之后就可進(jìn)行規(guī)范化.在該階段，利用匯總階段的計(jì)算結(jié)果將值傳遞階段得到的每個(gè)節(jié)點(diǎn)的權(quán)威值和中介值進(jìn)行數(shù)據(jù)規(guī)范化，公式如下：

(3)

(4)

式中，P為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中所有節(jié)點(diǎn)的集合.經(jīng)過數(shù)據(jù)歸一化階段后，所有節(jié)點(diǎn)的中介值和權(quán)威值都映射為0～1范圍的數(shù)值.然后循環(huán)迭代運(yùn)行值傳遞、匯總、規(guī)范化3個(gè)步驟，直至運(yùn)算結(jié)果的變化小于閾值，輸出結(jié)果.

2.3 X-RIME框架中HITS算法的數(shù)據(jù)結(jié)構(gòu)

HITS算法中每個(gè)節(jié)點(diǎn)需要有權(quán)威值和中介值2個(gè)屬性，每個(gè)屬性都有2個(gè)值，分別用來記錄當(dāng)前計(jì)算結(jié)果和上一輪運(yùn)算結(jié)果.在X-RIME框架中，通過標(biāo)簽Label數(shù)據(jù)結(jié)構(gòu)來記錄節(jié)點(diǎn)的屬性.本文通過HubLabel和AuthorityLabel兩個(gè)數(shù)據(jù)結(jié)構(gòu)模型來分別記錄節(jié)點(diǎn)的中介值和權(quán)威值.由于HITS算法是針對有向圖的，因此每個(gè)節(jié)點(diǎn)都有自己的前驅(qū)和后繼.在X-RIME框架中，采用LabeledAdjBiSetVertex類來表示圖中的節(jié)點(diǎn)，采用AdjVertexEdge類來表示圖中的邊.

3 HITS算法的分析與改進(jìn)

3.1 HITS算法分析

本文所研究的微博轉(zhuǎn)發(fā)網(wǎng)絡(luò)屬于社交網(wǎng)絡(luò)范疇，社交網(wǎng)絡(luò)的特點(diǎn)是每個(gè)用戶(節(jié)點(diǎn))之間社會(huì)屬性差異明顯[9-11].因此，在分析并挖掘微博信息傳播中的關(guān)鍵用戶時(shí)，區(qū)別每個(gè)用戶的社會(huì)屬性(粉絲數(shù)、活躍度等)顯得尤為重要.傳統(tǒng)HITS算法在值傳遞階段進(jìn)行節(jié)點(diǎn)初始化時(shí)，所有節(jié)點(diǎn)默認(rèn)的權(quán)威值和中介值都是1，沒有考慮不同節(jié)點(diǎn)中介值和權(quán)威值的社會(huì)屬性差異.在新浪微博轉(zhuǎn)發(fā)網(wǎng)絡(luò)中，不同節(jié)點(diǎn)的初始影響力是有差異的，這就需要考慮節(jié)點(diǎn)的社會(huì)屬性.因此，傳統(tǒng)HITS算法值傳遞階段節(jié)點(diǎn)初始化過程是可改進(jìn)的.

傳統(tǒng)HITS算法在值傳遞階段計(jì)算節(jié)點(diǎn)接受到的權(quán)威值和中介值時(shí)，只考慮了節(jié)點(diǎn)間連接的數(shù)量，即節(jié)點(diǎn)的入度和出度值，而沒有考慮節(jié)點(diǎn)間連接的社會(huì)屬性差異，即使節(jié)點(diǎn)的入度、出度值相同，但所連接節(jié)點(diǎn)的粉絲數(shù)、活躍度等社會(huì)屬性不同，需要綜合考慮節(jié)點(diǎn)和邊的社會(huì)屬性.因此，傳統(tǒng)HITS算法值傳遞階段節(jié)點(diǎn)接受權(quán)威值和中介值的過程也是可改進(jìn)的.本文將針對以上2個(gè)可改進(jìn)點(diǎn)提出改進(jìn)方案.

3.2 HITS算法改進(jìn)

首先，本文提出的加權(quán)HITS算法根據(jù)節(jié)點(diǎn)的綜合權(quán)值來確定節(jié)點(diǎn)的權(quán)威值和中介的初始值.在值傳遞階段將節(jié)點(diǎn)的社會(huì)屬性值進(jìn)行初始分配，計(jì)算節(jié)點(diǎn)和邊的社會(huì)屬性值，利用加權(quán)HITS算法計(jì)算新的權(quán)威值與中介值.加權(quán)HITS算法在匯總階段和規(guī)范化階段的執(zhí)行過程與傳統(tǒng)HITS算法一致.

由以上分析可知，加權(quán)HITS算法的改進(jìn)主要集中在值傳遞階段的初始化過程與值分配過程，體現(xiàn)在節(jié)點(diǎn)和邊的社會(huì)屬性差異.由于HITS算法要求所有的邊必須是有方向的，因此在計(jì)算過程中可通過A→B這樣一個(gè)指向關(guān)系和A，B兩個(gè)節(jié)點(diǎn)各自的社會(huì)屬性來計(jì)算邊的權(quán)值.

通過分析新浪微博提供的API發(fā)現(xiàn)，每個(gè)節(jié)點(diǎn)擁有可用來衡量自身社會(huì)屬性權(quán)值的朋友數(shù)、粉絲數(shù)、狀態(tài)數(shù)這3個(gè)屬性，分別用來表示節(jié)點(diǎn)所擁有的朋友數(shù)、粉絲數(shù)、發(fā)布的微博數(shù).對它們分別進(jìn)行統(tǒng)計(jì)運(yùn)算，用節(jié)點(diǎn)自身朋友數(shù)除以該傳播過程中所有節(jié)點(diǎn)的朋友數(shù)總和，可得到該節(jié)點(diǎn)對應(yīng)的朋友數(shù)權(quán)值，同理可求出每個(gè)節(jié)點(diǎn)對應(yīng)的權(quán)值.

3.3 加權(quán)HITS算法改進(jìn)與實(shí)現(xiàn)

3.3.1 加權(quán)HITS算法的改進(jìn)

節(jié)點(diǎn)的朋友數(shù)是指該節(jié)點(diǎn)有多少關(guān)注的好友，例如A關(guān)注B表示A成為B的粉絲，B成為A的朋友.朋友數(shù)越多說明這個(gè)節(jié)點(diǎn)關(guān)注的微博用戶越多，它能夠看到的新微博也越多，能夠?qū)π挛⒉┳鞒龌貞?yīng)的概率就越大.因此，朋友數(shù)越大的節(jié)點(diǎn)，其轉(zhuǎn)發(fā)能力越強(qiáng)，轉(zhuǎn)發(fā)微博的概率越大.

節(jié)點(diǎn)的粉絲數(shù)是指這個(gè)節(jié)點(diǎn)有多少人關(guān)注，粉絲越多，說明它發(fā)布的微博會(huì)被越多的人看到，微博被轉(zhuǎn)發(fā)的概率就越大.因此，粉絲數(shù)越多的節(jié)點(diǎn)，其發(fā)布能力越強(qiáng)，它發(fā)布的微博被轉(zhuǎn)發(fā)的概率就越大.

節(jié)點(diǎn)的狀態(tài)數(shù)表示這個(gè)節(jié)點(diǎn)發(fā)布過的微博數(shù)，發(fā)布的微博數(shù)量越多，說明這個(gè)節(jié)點(diǎn)越活躍，越活躍的節(jié)點(diǎn)會(huì)有更大的概率對其他節(jié)點(diǎn)產(chǎn)生影響.因此，狀態(tài)數(shù)越大的節(jié)點(diǎn)，它的活躍度越高，它發(fā)布的微博更容易被轉(zhuǎn)發(fā)，而且它也更容易轉(zhuǎn)發(fā)別人的微博.

在本文算法中，中介值和權(quán)威值分開考慮.中介值表示一個(gè)節(jié)點(diǎn)的中介度，如A→B，A轉(zhuǎn)發(fā)了B的微博，A的中介度得到提高，因此A的朋友數(shù)和狀態(tài)數(shù)影響到其中介值的計(jì)算，而B的粉絲數(shù)和狀態(tài)數(shù)也能影響A的中介值.在實(shí)際計(jì)算過程中，朋友數(shù)權(quán)值、粉絲數(shù)權(quán)值、狀態(tài)數(shù)權(quán)值的取值范圍均為區(qū)間(0,1).

3.3.2 加權(quán)HITS算法的設(shè)計(jì)與實(shí)現(xiàn)

本文通過面向?qū)ο蟮腏ava程序設(shè)計(jì)語言來實(shí)現(xiàn)加權(quán)HITS算法，該算法程序?qū)崿F(xiàn)的包結(jié)構(gòu)如圖1所示. 由圖可知，在HITSLabel包中，包括AuthorityLabel, HubLabel, VertexWeightLabel三個(gè)類.AuthorityLabel類用來標(biāo)記處理節(jié)點(diǎn)的權(quán)威值，HubLabel類用來標(biāo)記處理節(jié)點(diǎn)的中介值，VertexWeightLabel類用來標(biāo)記處理節(jié)點(diǎn)的權(quán)值屬性.HITSAlgorithm類是整個(gè)算法的全局控制類.創(chuàng)建DeliveryStep，HITSSummer，NormalizeStep類的實(shí)例，分別對應(yīng)值傳遞、匯總和規(guī)范化3個(gè)運(yùn)算階段.

圖1 加權(quán)HITS算法程序?qū)崿F(xiàn)的包結(jié)構(gòu)

在weightedHITS包中，包括加權(quán)HITS算法具體實(shí)現(xiàn)的所有類.加權(quán)HITS算法相比于原算法最大的改動(dòng)就是值傳遞階段，對應(yīng)DeliveryMapper類和DeliveryReducer類.Runner類是整個(gè)算法程序的入口，它通過創(chuàng)建一個(gè)HITSAlgorithm類的實(shí)例來開始算法的運(yùn)行.HITSAlgorithm類是整個(gè)算法的全局控制類，通過創(chuàng)建DeliveryStep，HITSSummer，NormalizeStep類的實(shí)例，分別對應(yīng)Delivery，Summer和Normalize三個(gè)運(yùn)算階段.HITSAlgorithm通過控制DeliveryStep，HITSSummer，NormalizeStep類的實(shí)例來控制整個(gè)算法的運(yùn)行.在DeliveryMapper類的map方法中，依次處理社交網(wǎng)絡(luò)中所有節(jié)點(diǎn)，直到所有節(jié)點(diǎn)的初始權(quán)威值和中介值都被分配完成.在DeliveryReducer類中有newhubScore，newauthorityScore，weightScore，friendScore，followerScore，statusScore六個(gè)參數(shù)記錄節(jié)點(diǎn)的社會(huì)屬性值.在DeliveryReducer類的reduce方法中，根據(jù)每個(gè)節(jié)點(diǎn)接收到的權(quán)威值、中介值、社會(huì)屬性權(quán)值，按照加權(quán)HITS算法計(jì)算出本節(jié)點(diǎn)的權(quán)威值與中介值.

在數(shù)據(jù)預(yù)處理過程中，將Pajek格式的數(shù)據(jù)文件導(dǎo)入X-Rime框架.在數(shù)據(jù)后處理過程中，根據(jù)每個(gè)節(jié)點(diǎn)收到的權(quán)威值、中介值和節(jié)點(diǎn)的權(quán)值，由HITSResultCalc類進(jìn)行節(jié)點(diǎn)數(shù)據(jù)的統(tǒng)計(jì)分析，當(dāng)達(dá)到加權(quán)HITS算法的停止條件后，由加權(quán)HITS算法排序得出所有節(jié)點(diǎn)的權(quán)威值和中介值排名.

3.4 加權(quán)HITS算法執(zhí)行結(jié)果的比較分析

本文選取4組微博信息傳播實(shí)驗(yàn)數(shù)據(jù)來測試加權(quán)HITS算法相對傳統(tǒng)HITS算法的優(yōu)勢，每組數(shù)據(jù)代表一條新浪微博的轉(zhuǎn)發(fā)傳播過程.表1是這4組數(shù)據(jù)對應(yīng)微博的基本信息.

表1 實(shí)驗(yàn)數(shù)據(jù)信息表

3.4.1 實(shí)驗(yàn)結(jié)果區(qū)分度比較

通過加權(quán)HITS算法發(fā)現(xiàn)社交網(wǎng)絡(luò)信息傳播過程中權(quán)威值和中介值排名較高的節(jié)點(diǎn)，對于4組實(shí)驗(yàn)數(shù)據(jù)分別進(jìn)行處理，各選取權(quán)威值和中介值排名前20的節(jié)點(diǎn)進(jìn)行對比分析.圖2是第1組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果對比.

由圖2可知，2種HITS算法得出的權(quán)威值前2名的結(jié)果是相同的，傳統(tǒng)HITS算法的第3名“chrisxw_待業(yè)青年”在加權(quán)HITS算法中排第5，傳統(tǒng)HITS算法中排第5名的“Joinin”在加權(quán)HITS算法中排第4名.加權(quán)HITS算法權(quán)威值計(jì)算結(jié)果與傳統(tǒng)HITS算法相比變化不大.但對比權(quán)威值的具體數(shù)值可發(fā)現(xiàn)，傳統(tǒng)HITS算法存在許多節(jié)點(diǎn)權(quán)威值相同的情況，如傳統(tǒng)HITS算法中第13～15名的權(quán)威值都是0.000 001 78，第16～20名的權(quán)威值都是0.000 000 89.而在加權(quán)HITS算法的運(yùn)算結(jié)果中，前20名的權(quán)威值沒有重復(fù)，說明改進(jìn)后的算法對節(jié)點(diǎn)權(quán)威值的區(qū)分度更高.改進(jìn)前后HITS算法計(jì)算得到的中介度結(jié)果差距較大.采用傳統(tǒng)HITS算法計(jì)算的第5～20名的中介值都是0.000 943 54.加權(quán)HITS算法的計(jì)算結(jié)果體現(xiàn)出區(qū)分度高的特點(diǎn)，前20名的中介值各不相同.而傳統(tǒng)HITS算法結(jié)果中有15個(gè)節(jié)點(diǎn)的中介值相同，導(dǎo)致2種HITS算法的計(jì)算結(jié)果排名差異較大.

(a) 傳統(tǒng)HITS算法

(b) 加權(quán)HITS算法

同理，通過分析中介值排名實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，加權(quán)HITS算法結(jié)果中用戶“山東嘉華文化國旅青島分社”排第7名，而在傳統(tǒng)HITS算法中并未進(jìn)入前20.對微博信息傳播數(shù)據(jù)分析發(fā)現(xiàn)，該用戶屬于一個(gè)旅行社官方微博，有許多與其關(guān)系很緊密的用戶，根據(jù)加權(quán)HITS算法計(jì)算公式，這些用戶相互之間的社會(huì)關(guān)系屬性權(quán)值較高.在計(jì)算中介值時(shí)，加權(quán)HITS算法考慮了用戶間的社會(huì)關(guān)系權(quán)值，使該用戶排名提高.

總之，加權(quán)HITS算法在結(jié)果區(qū)分度方面優(yōu)于傳統(tǒng)HITS算法，這是由于加權(quán)HITS算法考慮用戶自身社會(huì)屬性和用戶間關(guān)系社會(huì)屬性權(quán)值導(dǎo)致的.加權(quán)HITS算法相比于傳統(tǒng)HITS算法更適合對社交網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)進(jìn)行分析挖掘.

3.4.2 算法執(zhí)行效率比較

在驗(yàn)證程序執(zhí)行效率時(shí)，4組實(shí)驗(yàn)數(shù)據(jù)的算法執(zhí)行環(huán)境均為Hadoop云計(jì)算平臺，硬件配置為：華為RH2288H V3 機(jī)架式服務(wù)器，32 GB DDR4內(nèi)存，CPU型號Xeon E3-2609 ，采用Vmware虛擬機(jī)管理軟件配置3臺虛擬機(jī)，分別安裝Unbuntu 16操作系統(tǒng)，其中1臺虛擬機(jī)為Hadoop Namenode，其余2臺虛擬機(jī)為Hadoop Datanode.為比較算法執(zhí)行效率，2種HITS算法的運(yùn)行環(huán)境均一致，具體運(yùn)行效率情況如表2所示.

表2 加權(quán)HITS算法與傳統(tǒng)HITS算法運(yùn)行效率比較

由表2可知，在第1組、第2組和第4組實(shí)驗(yàn)中，傳統(tǒng)的HITS算法執(zhí)行了3次值傳遞、匯總和規(guī)范化過程，而加權(quán)HITS算法只執(zhí)行了2次相應(yīng)過程，加權(quán)HITS算法比傳統(tǒng)HITS算法的執(zhí)行效率提高了33.33%.第3組實(shí)驗(yàn)由于數(shù)據(jù)量較小，新舊算法的執(zhí)行效率差距不大.第4組實(shí)驗(yàn)數(shù)據(jù)量最大，二者執(zhí)行效率的差距也最大.傳統(tǒng)HITS算法運(yùn)行時(shí)間隨數(shù)據(jù)量增大而顯著增大，加權(quán)HITS算法在大數(shù)據(jù)量計(jì)算場景下具有相對優(yōu)勢，因此加權(quán)HITS算法更適合于大規(guī)模數(shù)據(jù)集的分析執(zhí)行.

為了驗(yàn)證算法在通用數(shù)據(jù)集上的執(zhí)行效果，本文在ego-Facebook數(shù)據(jù)集上分別執(zhí)行傳統(tǒng)HITS算法和加權(quán)HITS算法.ego-Facebook數(shù)據(jù)集來源于美國斯坦福大學(xué)的Stanford Network Analysis Project數(shù)據(jù)共享平臺[12]，是國內(nèi)外社交網(wǎng)絡(luò)算法研究中通用性較強(qiáng)的數(shù)據(jù)集.在ego-Facebook數(shù)據(jù)集上分別運(yùn)行傳統(tǒng)HITS算法和加權(quán)HITS算法的實(shí)現(xiàn)程序，傳統(tǒng)HITS算法執(zhí)行了6次值傳遞、匯總和規(guī)范化過程，而加權(quán)HITS算法執(zhí)行了4次值傳遞、匯總和規(guī)范化過程；傳統(tǒng)HITS算法執(zhí)行時(shí)間為758 s，加權(quán)HITS算法執(zhí)行時(shí)間為492 s，實(shí)驗(yàn)結(jié)果表明加權(quán)HITS算法具有較高的執(zhí)行效率.

因此，加權(quán)HITS算法在數(shù)據(jù)量較大情況下執(zhí)行效率明顯優(yōu)于傳統(tǒng)HITS算法.原因是加入了節(jié)點(diǎn)權(quán)值來描述節(jié)點(diǎn)間的社會(huì)關(guān)系，使得算法在初始化和運(yùn)算過程中能更準(zhǔn)確地計(jì)算節(jié)點(diǎn)的權(quán)威值中介值，從而減少算法迭代次數(shù)，提高執(zhí)行效率.在加權(quán)HITS算法的迭代過程中，節(jié)點(diǎn)的初始權(quán)值和社會(huì)屬性權(quán)值起到了加速迭代的作用，能讓算法更快地到達(dá)收斂狀態(tài)，減少了算法的迭代次數(shù)，提高了執(zhí)行效率.

4 結(jié)語

傳統(tǒng)HITS算法只考慮節(jié)點(diǎn)間連接關(guān)系，無法體現(xiàn)出微博社交網(wǎng)絡(luò)中節(jié)點(diǎn)和連接的社會(huì)屬性.加權(quán)HITS算法基于用戶自身和用戶間連接的社會(huì)屬性，將節(jié)點(diǎn)初始權(quán)值和連接邊權(quán)值引入HITS算法計(jì)算過程.本文在Hadoop云平臺環(huán)境下，基于X-Rime開源框提出加權(quán)HITS算法及軟件實(shí)現(xiàn)方案，并對算法的執(zhí)行結(jié)果進(jìn)行對比分析.實(shí)驗(yàn)結(jié)果表明，加權(quán)HITS算法由于充分考慮了社交網(wǎng)絡(luò)信息傳播過程中節(jié)點(diǎn)和邊的社會(huì)屬性，執(zhí)行效率提高，執(zhí)行結(jié)果具有更細(xì)的區(qū)分度.加權(quán)HITS算法在執(zhí)行效率和結(jié)果區(qū)分度上均優(yōu)于傳統(tǒng)HITS算法.