大規(guī)模社交網(wǎng)絡(luò)中高效的關(guān)鍵用戶選取方法

鄭永廣，岳 昆，尹子都，張學(xué)杰

(云南大學(xué) 信息學(xué)院，昆明 650500)

大規(guī)模社交網(wǎng)絡(luò)中高效的關(guān)鍵用戶選取方法

鄭永廣，岳 昆*，尹子都，張學(xué)杰

(云南大學(xué) 信息學(xué)院，昆明 650500)

針對(duì)大規(guī)模社交網(wǎng)絡(luò)及其用戶發(fā)布消息的歷史數(shù)據(jù)，如何快速有效地選取具有較強(qiáng)信息傳播能力的關(guān)鍵用戶，提出了一種關(guān)鍵用戶選取方法。首先，利用社交網(wǎng)絡(luò)的結(jié)構(gòu)信息，構(gòu)建以用戶為節(jié)點(diǎn)的有向圖，利用用戶發(fā)布消息的歷史數(shù)據(jù)，基于Spark計(jì)算框架，定量計(jì)算由用戶活躍度、轉(zhuǎn)發(fā)交互度和信息量占比刻畫的權(quán)重，從而構(gòu)建社交網(wǎng)絡(luò)的有向帶權(quán)圖模型; 然后，借鑒PageRank算法，建立用戶信息傳播能力的度量機(jī)制，給出基于Spark的大規(guī)模社交網(wǎng)絡(luò)中用戶信息傳播能力的計(jì)算方法; 進(jìn)而，給出基于Spark的d-距選取算法，通過多次迭代，使得所選取的不同關(guān)鍵用戶的信息傳播范圍盡量少地重疊。建立在新浪微博數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，所提方法具有高效性、可行性和可擴(kuò)展性，對(duì)于控制不良突發(fā)信息傳播、社交網(wǎng)絡(luò)輿情監(jiān)控具有一定的支撐作用。

大規(guī)模社交網(wǎng)絡(luò)；信息傳播能力；關(guān)鍵用戶；PageRank；Spark

0 引言

隨著在線社交網(wǎng)絡(luò)的迅速發(fā)展及移動(dòng)智能終端的迅速普及，社交網(wǎng)絡(luò)中信息的傳播對(duì)于國(guó)家和社會(huì)的影響日益深入，既給信息的傳遞和社交活動(dòng)帶來了便利，也可能構(gòu)成影響社會(huì)穩(wěn)定的隱患[1]，例如，在2011年爆發(fā)的“埃及革命”中，不法分子利用Twitter和Facebook等社交網(wǎng)絡(luò)使得騷亂極度放大[2]。以國(guó)內(nèi)新浪微博社交網(wǎng)絡(luò)為例，目前的注冊(cè)用戶已超過5億，每天有超過1億條微博內(nèi)容產(chǎn)生[3]，對(duì)于如此大規(guī)模社交網(wǎng)絡(luò)中的信息傳播，如何快速、及時(shí)地發(fā)現(xiàn)當(dāng)前社會(huì)熱點(diǎn)事件或不良社會(huì)思潮，具有重要意義[4]。

由于在線社交網(wǎng)絡(luò)是典型的小世界網(wǎng)絡(luò)，具有較短的平均路徑長(zhǎng)度和較高的聚類系數(shù)[5]，社交網(wǎng)絡(luò)的小世界現(xiàn)象和級(jí)聯(lián)式傳播方式具有很強(qiáng)的放大作用[6]，因此某種信息在社交網(wǎng)絡(luò)上的某個(gè)節(jié)點(diǎn)或多個(gè)節(jié)點(diǎn)傳播，極有可能引起很大的社會(huì)影響。識(shí)別網(wǎng)絡(luò)中最有影響的傳播者、選取具有較強(qiáng)信息傳播能力的關(guān)鍵用戶，對(duì)于確保信息有效傳播[7]、信息傳播控制和輿情監(jiān)控具有重要意義[8]。針對(duì)大規(guī)模社交網(wǎng)絡(luò)，信息傳播數(shù)量大，關(guān)鍵用戶的選取也具有相當(dāng)?shù)奶魬?zhàn)。

對(duì)此，本文綜合考慮以用戶作為節(jié)點(diǎn)的大規(guī)模社交網(wǎng)絡(luò)的有向圖結(jié)構(gòu)信息，以及用戶發(fā)布消息的歷史數(shù)據(jù)，重點(diǎn)考慮影響用戶信息傳播能力的因素，研究用于快速有效地選取大規(guī)模社交網(wǎng)絡(luò)中關(guān)鍵用戶的方法，為突發(fā)信息傳播控制和社交網(wǎng)絡(luò)輿情監(jiān)控等問題提供支撐技術(shù)。

近年來，研究人員針對(duì)社交網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)問題，從不同的角度提出了不同的方法。早期的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)計(jì)算，以Kempe等[9]提出的貪心算法為代表，由于算法時(shí)間復(fù)雜度較高，隨后出現(xiàn)了各種改進(jìn)的貪心算法和啟發(fā)式算法，如CELF(Cost-Effective Lazy Forward selection)[10]和DegreeDiscount[11]算法，這些算法面對(duì)大規(guī)模社交網(wǎng)絡(luò)時(shí)效率仍然較低，并且這些算法主要考慮社交網(wǎng)絡(luò)結(jié)構(gòu)，而用戶信息傳播能力的定量度量機(jī)制，仍有待進(jìn)一步研究。

從社交網(wǎng)絡(luò)用戶影響力度量的角度，研究人員提出了意見領(lǐng)袖發(fā)現(xiàn)或識(shí)別方法。例如: 文獻(xiàn)[12]從熱門消息傳播趨勢(shì)預(yù)測(cè)的角度，提出基于消息傳播的微博意見領(lǐng)袖影響力建模與測(cè)量分析方法；文獻(xiàn)[13]基于微博文本數(shù)據(jù)分析，從結(jié)構(gòu)、行為和情感三個(gè)維度度量用戶影響力，從而識(shí)別意見領(lǐng)袖。針對(duì)大規(guī)模社交網(wǎng)絡(luò)的意見領(lǐng)袖影響力建模技術(shù)，仍有待進(jìn)一步研究；同時(shí)，針對(duì)社交網(wǎng)絡(luò)中突發(fā)事件和不良突發(fā)信息檢測(cè)等問題，發(fā)現(xiàn)具有較強(qiáng)信息傳播能力的關(guān)鍵用戶，與意見領(lǐng)袖識(shí)別具有同樣重要的意義。

從社交網(wǎng)絡(luò)中用戶關(guān)系建模角度，文獻(xiàn)[14]以貝葉斯網(wǎng)作為社交網(wǎng)絡(luò)中用戶之間依賴關(guān)系表示和推演的知識(shí)模型，利用模型的結(jié)構(gòu)特征和貝葉斯網(wǎng)的概率推理機(jī)制，提出了用于關(guān)鍵用戶發(fā)現(xiàn)的MapReduce算法，但僅考慮了網(wǎng)絡(luò)結(jié)構(gòu)信息。文獻(xiàn)[15]考慮用戶交互影響及其動(dòng)態(tài)衰減，提出基于霍克斯過程的社交網(wǎng)絡(luò)中用戶關(guān)系強(qiáng)度模型及預(yù)測(cè)方法，但對(duì)于支持社交網(wǎng)絡(luò)中突發(fā)事件檢測(cè)的用戶信息傳播能力度量，還需進(jìn)一步研究，并且針對(duì)大規(guī)模社交網(wǎng)絡(luò)的建模和度量方法的效率仍需進(jìn)一步提升。

因此，為了在大規(guī)模社交網(wǎng)絡(luò)中快速有效地選取關(guān)鍵用戶，本文的研究面臨以下三方面的挑戰(zhàn)和問題：1)大規(guī)模社交網(wǎng)絡(luò)的高效計(jì)算；2)用戶信息傳播能力的有效度量；3)關(guān)鍵用戶的有效選取。

Spark是一個(gè)面向分布式海量數(shù)據(jù)分析、基于內(nèi)存的迭代計(jì)算通用框架[16]，其GraphX工具可以高效地執(zhí)行大規(guī)模圖的操作算法[17]，因此，針對(duì)問題1)，本文使用Spark作為數(shù)據(jù)處理框架，設(shè)計(jì)基于Spark的大規(guī)模社交網(wǎng)絡(luò)計(jì)算與處理算法。

PageRank[18]算法的核心思想是，每個(gè)節(jié)點(diǎn)的PageRank值，簡(jiǎn)稱PR值，取決于所有指向它的節(jié)點(diǎn)的PR值，且平均分配給它所指向的節(jié)點(diǎn)。然而，在社交網(wǎng)絡(luò)中，用戶(即節(jié)點(diǎn))的信息未必總是平均地傳播到它所指向的用戶，用戶之間相互關(guān)系的強(qiáng)度(例如不同用戶之間消息轉(zhuǎn)發(fā)頻度)，即節(jié)點(diǎn)之間邊上的權(quán)重，對(duì)信息傳播也具有重要的影響。因此，針對(duì)問題2)，首先基于用戶發(fā)布消息的歷史數(shù)據(jù)構(gòu)建帶權(quán)的社交網(wǎng)絡(luò)模型，然后借鑒PageRank算法并對(duì)其進(jìn)行擴(kuò)展，從而有效地度量用戶節(jié)點(diǎn)的信息傳播能力。

針對(duì)問題3)，為了使選取的用戶可以有效地用于檢測(cè)社交網(wǎng)絡(luò)中的突發(fā)信息或輿情監(jiān)控，本文提出了d-距選取算法，其核心思想是通過多次迭代使得所選取用戶之間的最短路徑長(zhǎng)度大于參數(shù)d，使得所選取的關(guān)鍵用戶的信息傳播范圍盡量少地重疊。

總的來說，本文的主要工作概括如下：

1)利用社交網(wǎng)絡(luò)的結(jié)構(gòu)信息，構(gòu)建以用戶為節(jié)點(diǎn)的有向圖，利用用戶發(fā)布消息的歷史數(shù)據(jù)，基于Spark定量計(jì)算由用戶活躍度、轉(zhuǎn)發(fā)交互度和信息量占比刻畫的權(quán)重，從而構(gòu)建社交網(wǎng)絡(luò)的有向帶權(quán)圖模型。

2)基于大規(guī)模的有向帶權(quán)社交網(wǎng)絡(luò)模型，通過用戶粉絲節(jié)點(diǎn)對(duì)其信息傳播能力貢獻(xiàn)值的累加來衡量用戶的信息傳播能力，借鑒并擴(kuò)展PageRank算法，給出基于Spark的節(jié)點(diǎn)信息傳播能力的度量方法。

3)針對(duì)突發(fā)信息檢測(cè)和輿情監(jiān)控等應(yīng)用中選取關(guān)鍵用戶的高效性和有效性需求，給出基于Spark的d-距選取算法，通過多次迭代，快速選取關(guān)鍵用戶，且不同關(guān)鍵用戶的信息傳播范圍盡量少地重疊。

4)建立在新浪微博數(shù)據(jù)集和Spark分布式集群上的實(shí)驗(yàn)，測(cè)試了本文方法的高效性、可行性和可擴(kuò)展性。

1 社交網(wǎng)絡(luò)模型構(gòu)建

不失一般性，本文用帶權(quán)有向圖G=(V,E)作為社交網(wǎng)絡(luò)模型[19]，其中，V為節(jié)點(diǎn)集(|V|=n)，節(jié)點(diǎn)表示社交網(wǎng)絡(luò)中的用戶；E為有向邊的集合，邊表示用戶之間的關(guān)注關(guān)系，從vi到vj的有向邊上的權(quán)重wij表示vi對(duì)vj信息傳播能力的貢獻(xiàn)(1≤i,j≤n,i≠j)。一個(gè)包含3個(gè)用戶的社交網(wǎng)絡(luò)如圖1所示。

圖1 帶有邊上權(quán)重的社交網(wǎng)絡(luò)模型Fig. 1 Social network model with weights on edges

用戶發(fā)布消息的歷史數(shù)據(jù)中，一條記錄的基本信息包含用戶、內(nèi)容、時(shí)間及來源，可表示為Item=(vi,c,t,f)。其中:vi表示用戶，c表示消息內(nèi)容，t表示消息發(fā)布時(shí)間;f用以標(biāo)識(shí)消息的來源，若f=0表示該消息為用戶原創(chuàng)，否則表示轉(zhuǎn)自其他用戶?；趫D1中的社交網(wǎng)絡(luò)，用戶歷史消息數(shù)據(jù)片段如表1所示。

表1 用戶歷史消息數(shù)據(jù)片段Tab. 1 Fragments of user historical messages

G中有向邊上的權(quán)重定量地刻畫了存在直接關(guān)注關(guān)系的用戶之間的信息傳播關(guān)系，是定量度量用戶信息傳播能力的基礎(chǔ)，對(duì)此，本文選擇與信息擴(kuò)散和用戶相互影響的主要因素作為用戶之間權(quán)重的度量指標(biāo)，即用戶活躍度、轉(zhuǎn)發(fā)交互度、以及信息量占比。進(jìn)而，可利用用戶的歷史消息定量地計(jì)算上述3個(gè)指標(biāo)的值，從而得到G中邊上的權(quán)重。

1.1 度量指標(biāo)定義

1.1.1 用戶活躍度

用戶活躍度記為a(vi)，通過用戶在一段時(shí)間內(nèi)所發(fā)布信息量d(vi)和轉(zhuǎn)發(fā)率r(vi)兩個(gè)方面來衡量，反映用戶對(duì)信息傳播的活躍情況，如式(1)：

(1)

其中：nrp(vi)與np(vi)分別表示用戶在這段時(shí)間內(nèi)所轉(zhuǎn)發(fā)的信息量、發(fā)布的信息量，通過用戶歷史消息數(shù)據(jù)統(tǒng)計(jì)計(jì)算得到；p為時(shí)間段長(zhǎng)度。

1.1.2 轉(zhuǎn)發(fā)交互度

轉(zhuǎn)發(fā)交互度記為eij，由用戶vi轉(zhuǎn)發(fā)vj消息的概率pij和vj對(duì)vi的重要程度zij決定，體現(xiàn)用戶對(duì)于信息轉(zhuǎn)發(fā)的交互在其關(guān)注節(jié)點(diǎn)上的差異，如式(2)：

(2)

其中，nrp(vi→vj)表示節(jié)點(diǎn)vi轉(zhuǎn)發(fā)vj的信息量，通過用戶歷史消息數(shù)據(jù)統(tǒng)計(jì)計(jì)算得到。

1.1.3 信息量占比

若社交網(wǎng)絡(luò)中節(jié)點(diǎn)vi的某段時(shí)間所發(fā)信息量為np(vi)、其關(guān)注為節(jié)點(diǎn)vj，則vj發(fā)布的信息量在vi所關(guān)注節(jié)點(diǎn)發(fā)布信息總量的占比為hij，如式(3)：

(3)

其中fri(vi)表示節(jié)點(diǎn)vi所關(guān)注節(jié)點(diǎn)的集合。

1.2 權(quán)重計(jì)算

前述3個(gè)指標(biāo)中，用戶活躍是信息傳播的誘因，信息量占比反映的是用戶之間的影響程度，在用戶活躍與用戶之間有影響的情況下，進(jìn)而通過轉(zhuǎn)發(fā)交互才能向其他用戶貢獻(xiàn)自己的信息傳播能力，因此本文將這3個(gè)指標(biāo)的值相乘來度量節(jié)點(diǎn)之間信息傳播能力的貢獻(xiàn)，即社交網(wǎng)絡(luò)中邊上的權(quán)重，vi到vj的有向邊上的權(quán)重wij由式(4)計(jì)算：

(4)

例1 為了確定圖1中社交網(wǎng)絡(luò)各有向邊上的權(quán)重，首先對(duì)形如表1中的數(shù)據(jù)片段進(jìn)行統(tǒng)計(jì)計(jì)算，得到如表2所示的統(tǒng)計(jì)信息，其中，“v2:2”表示來自節(jié)點(diǎn)v2的轉(zhuǎn)發(fā)量，式(4)中參數(shù)p的值為1，則可得到w12、w13、w21和w23的值分別為0.67、0.17、0.67和0.17。

表2 節(jié)點(diǎn)統(tǒng)計(jì)信息Tab. 2 Statistics of nodes

注：—表示該節(jié)點(diǎn)沒有對(duì)其他節(jié)點(diǎn)的信息進(jìn)行轉(zhuǎn)發(fā)。

2 基于信息傳播能力的關(guān)鍵用戶選取

2.1 節(jié)點(diǎn)信息傳播能力計(jì)算

節(jié)點(diǎn)信息傳播能力，以定量的方式反映了社交網(wǎng)絡(luò)模型中某一節(jié)點(diǎn)對(duì)信息傳播的作用，其值為其所有粉絲節(jié)點(diǎn)對(duì)其信息傳播能力貢獻(xiàn)值的累加。在此，本文借鑒PageRank算法[18]，采用NodeCapacity算法計(jì)算節(jié)點(diǎn)的信息傳播能力，簡(jiǎn)記為NC，其核心思想是:在社交網(wǎng)絡(luò)模型中，每個(gè)節(jié)點(diǎn)的NC值為其所有粉絲節(jié)點(diǎn)對(duì)其貢獻(xiàn)值的累加，每個(gè)節(jié)點(diǎn)的NC值以邊上權(quán)重的形式貢獻(xiàn)給它關(guān)注的節(jié)點(diǎn)，如式(5)所示：

(5)

其中：nci表示節(jié)點(diǎn)vi的信息傳播能力；foll(vi)表示關(guān)注節(jié)點(diǎn)vi的節(jié)點(diǎn)集；wji表示節(jié)點(diǎn)vj對(duì)vi信息傳播能力的貢獻(xiàn)權(quán)重；q為阻尼系數(shù)，q∈(0, 1)。

針對(duì)大規(guī)模的帶權(quán)社交網(wǎng)絡(luò)，本文首先使用Spark中用于圖操作的aggregateMessage方法，將各節(jié)點(diǎn)其粉絲節(jié)點(diǎn)的NC值以邊上的權(quán)重匯聚并作為其NC值，然后基于圖操作joinVertices方法將匯聚后的值更新為相應(yīng)節(jié)點(diǎn)的NC值，依此進(jìn)行多次迭代操作，上述思想由算法1給出。

算法1 NodeCapacity。

輸入G為帶權(quán)社交網(wǎng)絡(luò)圖，N為給定的迭代次數(shù)閾值。

輸出NG為帶有節(jié)點(diǎn)NC值的社交網(wǎng)絡(luò)圖。

1)

varg←G

2)

variteration← 0

3)

varpG: Graph[Double, Double] ← null

/*用于釋放緩存的圖RDD*/

4)

WHILEiteration

5)

g.cache()

/*緩存圖RDD*/

6)

varupdates←g.aggregateMessage[Double](ctx=>

ctx.sendToDst(ctx.srcAttr *ctx.attr), _ + _,

TripletFields.Src)

/*匯聚其粉絲節(jié)點(diǎn)的貢獻(xiàn)值*/

7)

pG←g

8)

g← g.joinVertices(updates) { (id,oldAr,msgSum) =>

(1.0-q) +q*msgSum}

/*更新圖節(jié)點(diǎn)中的NC值*/

9)

pG.unpersist(false)

/*釋放圖RDD*/

10)

iteration←iteration+1

11)

END WHILE

12)

NG←g

算法1的執(zhí)行代價(jià)主要取決于步驟6)和8)中的圖操作，其執(zhí)行代價(jià)取決于社交網(wǎng)絡(luò)中節(jié)點(diǎn)及其粉絲節(jié)點(diǎn)數(shù)，時(shí)間復(fù)雜度為O(mn)，因此，算法1的時(shí)間復(fù)雜度為O(lmn)，其中，l為算法迭代次數(shù)，m為每個(gè)節(jié)點(diǎn)的平均粉絲節(jié)點(diǎn)數(shù)，n為社交網(wǎng)絡(luò)中所包含的節(jié)點(diǎn)數(shù)。此外，算法1的收斂性與PageRank算法相同，二者的主要區(qū)別僅在于節(jié)點(diǎn)對(duì)于其關(guān)注節(jié)點(diǎn)的貢獻(xiàn)的分配方式，PageRank算法根據(jù)節(jié)點(diǎn)的出鏈數(shù)進(jìn)行平均分配，而算法1按照邊上的權(quán)重進(jìn)行分配。

例2 針對(duì)圖1中的社交網(wǎng)絡(luò)，假設(shè)節(jié)點(diǎn)v1、v2和v3的當(dāng)前NC值分別為nc1、nc2和nc3，算法1的一次迭代操作為：首先由步驟6)得到各節(jié)點(diǎn)的匯聚值upNci，若upNc1為nc2*w21、upNc2為nc1*w12、upNc3為nc1*w13+nc2*w23，則由步驟8)，用節(jié)點(diǎn)的匯聚值更新相應(yīng)節(jié)點(diǎn)的NC值，得到新的NC值，節(jié)點(diǎn)v1的NC值為(1.0-q)+q*upNc1。

2.2 關(guān)鍵用戶選取

對(duì)于社交網(wǎng)絡(luò)G=(V,E)，本文希望從V中選取關(guān)鍵節(jié)點(diǎn)集S，S?V，|S|=k，使得S中的節(jié)點(diǎn)在G中具有盡量大的信息傳播范圍，即能夠盡量多地影響到其他節(jié)點(diǎn)。首先，關(guān)鍵節(jié)點(diǎn)應(yīng)該具有較大的信息傳播能力，即具有較大的NC值；其次，不同關(guān)鍵節(jié)點(diǎn)的信息傳播范圍應(yīng)該盡量少地重疊。若給定節(jié)點(diǎn)的信息傳播范圍閾值d，則節(jié)點(diǎn)vi的信息傳播范圍可用從vi出發(fā)經(jīng)過長(zhǎng)度不超過d的路徑可到達(dá)的節(jié)點(diǎn)集來描述。

因此，為了高效地選取關(guān)鍵節(jié)點(diǎn)，在選取G中的k個(gè)關(guān)鍵節(jié)點(diǎn)時(shí)，每次選取當(dāng)前具有最大NC值的節(jié)點(diǎn)，然后將該節(jié)點(diǎn)及與其之間路徑長(zhǎng)度不大于d的節(jié)點(diǎn)進(jìn)行標(biāo)記，不作為待選取的關(guān)鍵節(jié)點(diǎn)，從而使得選取的節(jié)點(diǎn)之間的路徑長(zhǎng)度都大于d，經(jīng)過k次迭代，可高效地選取k個(gè)關(guān)鍵節(jié)點(diǎn)(即關(guān)鍵用戶)。根據(jù)社交網(wǎng)絡(luò)的小世界特性，將d的取值范圍設(shè)為1～6。

針對(duì)大規(guī)模社交網(wǎng)絡(luò)，本文基于Spark實(shí)現(xiàn)上述關(guān)鍵用戶選取的思想，稱為d-距選取算法。首先，向圖的reduce操作傳入一個(gè)比較函數(shù)，進(jìn)而選取出當(dāng)前具有最大NC值的節(jié)點(diǎn)、并將其作為關(guān)鍵節(jié)點(diǎn)；然后，將與所選取節(jié)點(diǎn)之間路徑長(zhǎng)度不大于d的所有節(jié)點(diǎn)的NC值都置為0；接著，使用圖的subgraph操作去除NC值為0的節(jié)點(diǎn)，以生成一個(gè)新的子圖，如此進(jìn)行多次迭代操作。上述思想見算法2。

算法2d-距選取。

輸入G為帶有NC值的圖G=(V,E)(由算法1得到),k為關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)，d為路徑長(zhǎng)度。

輸出S為關(guān)鍵節(jié)點(diǎn)集合。

1)

varg←G

2)

varS← new ListBuffer[(Long, Double)]

/*保存關(guān)鍵節(jié)點(diǎn)*/

3)

varpG: Graph[Double, Double] ← null

/*用于釋放緩存的圖RDD*/

4)

def max(a,b)

/*定義一個(gè)比較函數(shù)*/

5)

FORi← 0 TOkDO

/*選取k個(gè)關(guān)鍵節(jié)點(diǎn)*/

6)

vart←g.vertices.reduce((a,b) =>max(a,b))

/*選取具有最大NC值的節(jié)點(diǎn)*/

7)

S←S∪{t}

/*將選取的節(jié)點(diǎn)t添加到S中*/

8)

pG←g

9)

FORj← 1 TOdDO

10)

g← 將與節(jié)點(diǎn)t的最短路徑長(zhǎng)度小于等于j的所有節(jié)點(diǎn)的NC值置為0

11)

END FOR

12)

g←g.subgraph(vpred=(id,attr)=>attr> 0.0)

/*從g中去除NC值為0的節(jié)點(diǎn)*/

13)

pG.unpersist(false)

14)

END FOR

15)

RETURNS

/*返回關(guān)鍵節(jié)點(diǎn)集*/

算法2的執(zhí)行代價(jià)主要取決于步驟5)～14)中圖操作執(zhí)行時(shí)節(jié)點(diǎn)、關(guān)注節(jié)點(diǎn)及其粉絲節(jié)點(diǎn)的數(shù)量，步驟6)中圖操作的時(shí)間復(fù)雜度為O(n)，步驟9)～11)的時(shí)間復(fù)雜度為O(dmn)，步驟12中圖操作的時(shí)間復(fù)雜度為O(mn)，因此，算法2的時(shí)間復(fù)雜度為O(kdmn)。其中，k為選取的關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)，d為路徑長(zhǎng)度，m為平均每個(gè)節(jié)點(diǎn)的粉絲節(jié)點(diǎn)數(shù)，n為社交網(wǎng)絡(luò)模型中包含的節(jié)點(diǎn)數(shù)。

例3 針對(duì)圖1中的社交網(wǎng)絡(luò)，若節(jié)點(diǎn)v2的NC值為當(dāng)前最大值，若閾值d為1，算法2執(zhí)行時(shí)的一次循環(huán)操作為：首先，由步驟6)選取節(jié)點(diǎn)v2，由步驟7)將v2加入到關(guān)鍵節(jié)點(diǎn)集S中，然后由步驟8)～11)將節(jié)點(diǎn)v2、v1和v3的NC值設(shè)為0，由步驟12)去除這些NC值為0的節(jié)點(diǎn)，從而以生成一個(gè)新的子圖，以進(jìn)行下一次迭代操作。

3 實(shí)驗(yàn)結(jié)果

為了測(cè)試本文算法的有效性，在Spark集群環(huán)境下實(shí)現(xiàn)了本文方法，采用新浪微博數(shù)據(jù)集進(jìn)行性能測(cè)試。首先從數(shù)據(jù)堂(http://www.datatang.com/detail/6)下載微博用戶關(guān)系數(shù)據(jù)集，從中提取出度數(shù)大于10的節(jié)點(diǎn)，形成一個(gè)社交網(wǎng)絡(luò)，然后使用網(wǎng)絡(luò)爬蟲技術(shù)抓取用戶發(fā)布的消息數(shù)據(jù)。數(shù)據(jù)集包含4 269 813個(gè)用戶節(jié)點(diǎn)，共有69 060 604條反映用戶之間關(guān)系的邊，包括67 432 812條2016年5月的用戶消息歷史數(shù)據(jù)集，大小為10.75 GB；集群環(huán)境由1個(gè)Master節(jié)點(diǎn)和10個(gè)Worker節(jié)點(diǎn)組成，其中Master節(jié)點(diǎn)CPU為4核、2.2 GHz主頻、32 GB內(nèi)存，Worker節(jié)點(diǎn)CPU為2核、2.2 GHz主頻、16 GB 內(nèi)存。我們首先測(cè)試了關(guān)鍵用戶選取結(jié)果的有效性，然后測(cè)試了算法1和算法2的執(zhí)行時(shí)間、加速比和并行效率。

3.1 有效性測(cè)試

為了測(cè)試?yán)帽疚姆椒ㄋx取關(guān)鍵用戶的有效性，根據(jù)新浪微博輿情系統(tǒng)2016年6月熱點(diǎn)輿情報(bào)告(http://blog.sina.com.cn/s/blog_ec0961940102wn59.html)中的TOP-10社會(huì)熱點(diǎn)事件，對(duì)所選取關(guān)鍵用戶的有效性進(jìn)行評(píng)測(cè)，測(cè)試指標(biāo)包括捕捉率(Catch Ratio, CR)和捕捉收益(Catch Profit, CP)，其中CR為通過選取的關(guān)鍵用戶檢測(cè)到的突發(fā)信息與網(wǎng)絡(luò)中實(shí)際存在的突發(fā)信息的比值，CP為通過選取的關(guān)鍵用戶對(duì)突發(fā)信息的檢測(cè)而可遏制信息量所占比例。這兩個(gè)評(píng)價(jià)指標(biāo)的值越大，說明選取的關(guān)鍵用戶的有效性越大。

首先測(cè)試關(guān)鍵用戶數(shù)量k和路徑長(zhǎng)度閾值d對(duì)CR的影響，如圖2所示?？梢钥闯觯琸與d對(duì)CR的影響較大；當(dāng)d為2時(shí)，隨著關(guān)鍵用戶數(shù)量k的增加，CR值穩(wěn)定增大，基于本文的方法選取關(guān)鍵用戶的有效性更加顯著。

圖2 不同路徑長(zhǎng)度閾值下的CR指標(biāo)Fig. 2 CR under various route length thresholds

然后將本文中關(guān)鍵用戶選取結(jié)果與基于PageRank[18]和DegreeDiscount[11]進(jìn)行關(guān)鍵用戶選取的結(jié)果進(jìn)行比較，測(cè)試了不同方法的CR和CP，其中將本文方法中路徑長(zhǎng)度閾值d設(shè)置為2。圖3給出了關(guān)鍵用戶數(shù)量為10、20、30、40和50的情況下，本文方法、PageRank及DegreeDiscount算法對(duì)CR的影響?？梢钥闯?，隨著關(guān)鍵用戶數(shù)量的增加，本文方法的CR明顯優(yōu)于PageRank及DegreeDiscount算法。

圖3 不同算法下CR指標(biāo)比較Fig. 3 CR comparison of various algorithms

進(jìn)一步測(cè)試本文提出的關(guān)鍵用戶選取方法對(duì)新浪微博社交網(wǎng)絡(luò)中的真實(shí)突發(fā)事件檢測(cè)的CP，如圖4所示。事件1～事件6分別為“小學(xué)生當(dāng)街鬧分手”“8名江西高中老師為學(xué)生出征壯行”“六一媽媽偷雞腿給生病女兒”“網(wǎng)現(xiàn)史上最強(qiáng)的考研指導(dǎo)”“西安南郊變電站閃爆”及“上海浦東機(jī)場(chǎng)T2航站樓發(fā)生爆炸”。由圖4可以看出，基于本文方法、PageRank及DegreeDiscount算法選取的關(guān)鍵用戶檢測(cè)到的評(píng)測(cè)事件有所差異，在捕捉到的情況下，各方法的捕捉收益CP基本都在0.75以上，不少情形達(dá)到了0.9以上，表明這三種方法選取的關(guān)鍵用戶可以較早地檢測(cè)到評(píng)測(cè)事件的傳播，進(jìn)而可以對(duì)事件的擴(kuò)散有很好的控制。這說明本文提出的關(guān)鍵用戶選取方法，對(duì)于用來檢測(cè)社交網(wǎng)絡(luò)中的突發(fā)事件是有效的。

圖4 不同算法下CP指標(biāo)比較Fig. 4 CP comparison of various algorithms

3.2 效率測(cè)試

為了測(cè)試算法1和算法2的執(zhí)行效率，本文將數(shù)據(jù)集劃分為規(guī)模為2.2 GB、4.4 GB、6.6 GB、8.8 GB和11 GB的5個(gè)數(shù)據(jù)塊，基于這5個(gè)數(shù)據(jù)塊構(gòu)建相應(yīng)的邊數(shù)逐漸增加的有向帶權(quán)社交網(wǎng)絡(luò)模型，ID分別為1、2、3、4和5，節(jié)點(diǎn)數(shù)和邊數(shù)如表3所示。

表3 社交網(wǎng)絡(luò)模型的節(jié)點(diǎn)和邊數(shù)Tab. 3 Number of nodes and edges in social network models

在Worker數(shù)(計(jì)算節(jié)點(diǎn))為1、2、4和8的情況下，本文分別在這5個(gè)社交網(wǎng)絡(luò)模型之上，對(duì)算法1和算法2的執(zhí)行時(shí)間、加速比和并行效率進(jìn)行了測(cè)試。通過反復(fù)測(cè)試，將迭代次數(shù)閾值設(shè)為10，此時(shí)節(jié)點(diǎn)信息傳播能力的計(jì)算收斂；將d和k分別設(shè)置為2和50。

算法1和算法2基于不同規(guī)模的社交網(wǎng)絡(luò)模型在不同Worker數(shù)下的執(zhí)行時(shí)間如圖5所示。

圖5 算法的執(zhí)行時(shí)間Fig. 5 Execution time of algorithm

可以看出，算法1和算法2的執(zhí)行時(shí)間在同一Worker數(shù)量下隨著社交網(wǎng)絡(luò)規(guī)模的增大而呈線性增長(zhǎng)；社交網(wǎng)絡(luò)規(guī)模一定時(shí)，執(zhí)行時(shí)間隨著Worker數(shù)量的增多而明顯減少，說明算法1和算法2在數(shù)據(jù)規(guī)模增大時(shí)，可以通過增加Worker數(shù)來大幅降低其執(zhí)行時(shí)間，即能有效地處理大規(guī)模社交網(wǎng)絡(luò)。

加速比是算法在1個(gè)Worker節(jié)點(diǎn)與多個(gè)Worker節(jié)點(diǎn)情形下執(zhí)行時(shí)間的比值。在不同規(guī)模的社交網(wǎng)絡(luò)上、不同Worker數(shù)情形下，算法1和算法2的加速比如圖6所示。可以看出，社交網(wǎng)絡(luò)規(guī)模一定時(shí)，加速比隨著Worker數(shù)量的增多而明顯增大。當(dāng)Worker數(shù)為2時(shí)，加速比均接近1.5；當(dāng)Worker數(shù)為8時(shí)，加速比隨著社交網(wǎng)絡(luò)規(guī)模的增大而明顯增加，說明算法1和算法2具有較好的并行性和可擴(kuò)展性。

圖6 算法的加速比Fig. 6 Speedup of algorithm

并行效率是算法加速比與Worker數(shù)的比值。在不同規(guī)模的社交網(wǎng)絡(luò)上、不同Worker數(shù)情形下，算法1和算法2的并行效率如圖7所示?？梢钥闯?，算法1和算法2的并行效率在同一Worker數(shù)量下，隨著社交網(wǎng)絡(luò)規(guī)模的增大而緩慢增大，在Worker為2時(shí)，并行效率增大不明顯，主要是因?yàn)橐堰_(dá)到一個(gè)比較大的值，由于社交網(wǎng)絡(luò)規(guī)模劃分不均勻而造成并行效率和加速比的抖動(dòng)，說明算法1和算法2具有較好的并行性，且較適合處理大規(guī)模社交網(wǎng)絡(luò)。

圖7 算法的并行效率Fig. 7 Parallel efficiency of algorithm

4 結(jié)語(yǔ)

利用社交網(wǎng)絡(luò)的結(jié)構(gòu)信息和用戶發(fā)布消息的歷史數(shù)據(jù)，本文給出了社交網(wǎng)絡(luò)中用戶信息傳播能力的定量度量機(jī)制，提出了一種高效的大規(guī)模社交網(wǎng)絡(luò)中關(guān)鍵用戶的選取方法，并給出了基于Spark的算法實(shí)現(xiàn)。在新浪微博社交網(wǎng)絡(luò)真實(shí)數(shù)據(jù)集上，測(cè)試了本文所提出方法的可行性、高效性和可擴(kuò)展性。本文提出的關(guān)鍵用戶選取方法，可作為支撐技術(shù)用于解決大規(guī)模社交網(wǎng)絡(luò)中突發(fā)信息檢測(cè)和輿情監(jiān)控等問題。

然而，本文提出的用戶信息傳播能力度量和關(guān)鍵用戶選取方法，僅考慮用戶傳播消息的行為而未考慮傳播信息的內(nèi)容，因此可能產(chǎn)生消息主題漂移而選出“偽關(guān)鍵用戶”。為了使得選取的關(guān)鍵用戶更加準(zhǔn)確有效，基于社交網(wǎng)絡(luò)結(jié)構(gòu)信息，將用戶傳播消息的行為與用戶之間轉(zhuǎn)發(fā)交互的內(nèi)容結(jié)合起來，可進(jìn)一步完善關(guān)鍵用戶的性質(zhì)和選取方法。將社交網(wǎng)絡(luò)的影響最大化及種子節(jié)點(diǎn)選擇的已有方法用于本文中關(guān)鍵用戶的選取，對(duì)目前的方法進(jìn)行改進(jìn)，是將要開展的工作。

References)

[1] ZHAO Z, RESNICK P, MEI Q Z. Enquiring minds: early detection of rumors in social media from enquiry posts[C]// Proceedings of the 24th International Conference on World Wide Web. New York: ACM, 2015:1395-1405.

[2] 周東浩,韓文報(bào).DiffRank:一種新型社會(huì)網(wǎng)絡(luò)信息傳播檢測(cè)算法[J]. 計(jì)算機(jī)學(xué)報(bào),2014, 37(4):884-893. (ZHOU D H, HAN W B. DiffRank: a novel algorithm for information diffusion detection in social networks[J]. Chinese Journal of Computers, 2014, 37(4):884-893.)

[3] 曹玖新,吳江林,石偉,等.新浪微博網(wǎng)信息傳播分析與預(yù)測(cè)[J]. 計(jì)算機(jī)學(xué)報(bào),2014,37(4):779-790. (CAO J X, WU J L, SHI W, et al. Sina microblog information diffusion analysis and prediction[J]. Chinese Journal of Computers, 2014, 37(4):779-790.)

[4] BIAN J W, YANG Y, CHUA T S. Predicting trending messages and diffusion participants in microblogging network[C]// Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2014:537-546.

[5] 徐恪,張賽,陳昊,等.在線社會(huì)網(wǎng)絡(luò)的測(cè)量與分析[J]. 計(jì)算機(jī)學(xué)報(bào),2014,37(1):165-188. (XU K, ZHANG S, CHEN H, et al. Measurement and analysis of online social networks[J]. Chinese Journal of Computers, 2014,37(1):165-188.)

[6] 韓毅,許進(jìn),方濱興,等.社交網(wǎng)絡(luò)的結(jié)構(gòu)支撐理論[J]. 計(jì)算機(jī)學(xué)報(bào),2014,37(4):905-914. (HAN Y, XU J, FANG B X, et al. Structural supportiveness theory on social networks[J]. Chinese Journal of Computers, 2014,37(4):905-914.)

[7] GUILLE A, HACID H, FAVRE C, et al. Information diffusion in online social networks: a survey[J]. ACM SIGMOD Record, 2013,42(2):17-28.

[8] MAHMOODY A, RIONDATO M, UPFAL E. Wiggins: detecting valuable information in dynamic networks using limited resources [C]// Proceedings of the 9th ACM International Conference on Web Search and Data Mining. New York: ACM, 2016: 677-686.

[9] KEMPE D, KLEINBERG J, TARDOS E. Maximizing the spread of influence through a social network [C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003:137-146.

[10] LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 420-429.

[11] CHEN W, WANG Y J, YANG S Y. Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 199-208.

[12] 王晨旭,管曉宏,秦濤,等.微博消息傳播中意見領(lǐng)袖影響力建模與應(yīng)用研究[J]. 軟件學(xué)報(bào),2015,26(6):1473-1485.(WANG C X, GUAN X H, QIN T, et al. Modeling on opinion leader’s influence in microblog message propagation and its application[J]. Journal of Software, 2015, 26(6):1473-1485.)

[13] 曹玖新,陳高君,吳江林,等.基于多維特征分析的社交網(wǎng)絡(luò)意見領(lǐng)袖挖掘[J]. 電子學(xué)報(bào),2016,44(4):898-905. (CAO J X, CHEN G J, WU J L, et al. Multi-feature based opinion leader mining in social networks[J]. Acta Electronica Sinica, 2016, 44(4):898-905.)

[14] YUE K, WU H, FU X D, et al. A data-intensive approach for discovering user similarities in social behavioral interactions based on the Bayesian network[J]. Neurocomputing, 2017,219:364-375.

[15] 于巖,陳鴻昶,于洪濤.基于霍克斯過程的社交網(wǎng)絡(luò)用戶關(guān)系強(qiáng)度模型[J]. 電子學(xué)報(bào),2016,44(6):1362-1368.(YU Y, CHEN H C, YU H T. A social networks user relationship strength model based on Hawkes process[J]. Acta Electronica Sinica, 2016, 44(6):1362-1368.)

[16] ZAHARIA M. An architecture for fast and general data processing on large clusters[EB/OL].[2016- 11- 20]. http://digitalassets.lib.berkeley.edu/etd/ucb/text/Zaharia_berkeley_0028E_14121.pdf.

[17] XIN R S, GONZALEZ J E, FRANKLIN M J, et al. GraphX: a resilient distributed graph system on Spark[C]// Proceedings of the 1st International Workshop on Graph Data Management Experience and Systems. New York: ACM, 2013: Article No. 2.

[18] XIE W L, BINDEL D, DEMERS A, et al. Edge-weighted personalized PageRank: breaking a decade-old performance barrier[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2015: 1325-1334.

[19] 吳信東,李毅,李磊.在線社交網(wǎng)絡(luò)影響力分析[J].計(jì)算機(jī)學(xué)報(bào), 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.)

This work is partially supported by the National Natural Science Foundation of China (61472345, 61562090), the Key Program of Natural Science Foundation of Yunnan Province (2014FA023), the Program for the Second Batch of Yunling Scholars of Yunnan Province (C6153001), the Program for Excellent Young Talents of Yunnan University (WX173602), the Research Foundation of Educational Department of Yunnan Province (2016ZZX006, 2016YJS005).

ZHENGYongguang, born in 1988, M. S. candidate. His research interests include massive data analysis and services.

YUEKun, born in 1979, Ph. D., professor. His research interests include massive data analysis and services.

YINZidu, born in 1990, Ph. D. candidate. His research interests include massive data analysis and services.

ZHANGXuejie, born in 1965, Ph. D., professor. His research interests include distributed computing.

Efficientapproachforselectingkeyusersinlarge-scalesocialnetworks

ZHENG Yongguang, YUE Kun*, YIN Zidu, ZHANG Xuejie

(SchoolofInformationScienceandEngineering,YunnanUniversity,KunmingYunnan650500,China)

To select key users with great information dissemination capability efficiently and effectively from large-scale social networks and corresponding historical user massages, an approach for selecting key users was proposed. Firstly, the structure information of the social network was used to construct the directed graph with the user as the node. Based on the Spark calculation framework, the weights of user activity, transmission interaction and information quantity were quantitatively calculated by the historical data of the message, so as to construct a dynamic weighted graph model of social networks. Then, the measurement for user’s information dissemination capacity was established based on PageRank and the Spark-based algorithm was given correspondingly for large-scale social networks. Further more, the algorithm ford-distance selection of key users was given to make the overlap of information dissemination ranges of different key users be as less as possible by multiple iterations. The experimental results based on Sina Weibo datasets show that the proposed approach is efficient, feasible and scalable, and can provide underlying techniques to control the spread of bad news and monitor public opinions to a certain extent.

large-scale social network; information dissemination capacity; key user; PageRank; Spark

2017- 05- 16;

2017- 06- 05。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472345, 61562090); 云南省應(yīng)用基礎(chǔ)研究計(jì)劃重點(diǎn)項(xiàng)目(2014FA023); 第二批“云嶺學(xué)者”培養(yǎng)項(xiàng)目(C6153001); 云南大學(xué)青年英才培養(yǎng)計(jì)劃項(xiàng)目(WX173602); 云南省教育廳科研基金資助項(xiàng)目(2016ZZX006, 2016YJS005)。

鄭永廣(1988—)，男，河北邢臺(tái)人，碩士研究生，主要研究方向：海量數(shù)據(jù)分析與服務(wù)； 岳昆(1979—)，男，云南曲靖人，教授，博士生導(dǎo)師，博士，CCF高級(jí)會(huì)員，主要研究方向：海量數(shù)據(jù)分析與服務(wù)； 尹子都(1990—)，男，甘肅蘭州人，博士研究生，主要研究方向：海量數(shù)據(jù)分析與服務(wù)； 張學(xué)杰(1965—)，男，云南昆明人，教授，博士生導(dǎo)師，博士，主要研究方向：分布式計(jì)算。

1001- 9081(2017)11- 3101- 06

10.11772/j.issn.1001- 9081.2017.11.3101

(*通信作者電子郵箱kyue@ynu.edu.cn)

TP391.41

A