基于PageRank和最短路徑的用戶影響力評估

張俊豪

（鐵道警察學(xué)院公安技術(shù)系 河南 鄭州 450003）

1 引言

微博作為我國主流的社交網(wǎng)絡(luò)之一[1]，每一次社會輿論的醞釀、傳播、爆發(fā)都與其有著直接的關(guān)系，其中，微博中那些重要的微博用戶對輿論的引導(dǎo)、走向起著至關(guān)重要的作用。通過衡量微博用戶影響力可以挖掘出影響輿論發(fā)展的重要用戶、預(yù)測輿論的發(fā)展方向、確定微博網(wǎng)絡(luò)的核心框架以及為其他的研究奠定理論接觸等[2]。目前對用戶影響力的研究已經(jīng)取得了很大突破，根據(jù)算法種類可將前期研究分為4類：①基于PageRank的用戶影響力評估模型。主要有王彪的peoplerank算法[3]、陳少欽的實(shí)時用戶影響力算法等[4]。②基于微博行為的用戶影響力評估模型。主要有肖宇的基于用戶行為特性的評估模型[5]、齊超的三大網(wǎng)絡(luò)評估模型[6]、朱郭峰的主題行為評估模型[7]、Ye等人的行為對比評估模型等[8]。③基于路徑的用戶影響力評估模型。主要有郭浩等人的基于直接影響力和級聯(lián)影響力的用戶影響力評估模型[9]、陳燦的K-覆蓋度評估模型[10]。④其他用戶影響力評估模型。主要是利用博弈論、傳染病模型等進(jìn)行用戶影響力評估。

以上的評估模型各有優(yōu)缺點(diǎn)，但都未能從用戶所處微博中的關(guān)鍵位置出發(fā)去衡量用戶影響力。本文綜合運(yùn)用圖論、微博網(wǎng)絡(luò)特性、社會學(xué)等知識，提出一種基于PageRank和最短路徑的用戶影響力算法（User Influence Assessment Based on PageRank and Shortest Path，UIA-PSP）。

2 PageRank算法原理

PageRank算法通過網(wǎng)頁之間的鏈接關(guān)系得到網(wǎng)頁權(quán)值，算法主要有以下兩個核心思想[11]：

（1）一個網(wǎng)頁的鏈入鏈接越多，該網(wǎng)頁就越重要。

（2）一個高權(quán)威網(wǎng)頁鏈接至另一個網(wǎng)頁，那么被鏈接的網(wǎng)頁也非常重要。

PageRank算法的計(jì)算過程如圖1所示。

圖1 網(wǎng)頁結(jié)構(gòu)圖

假設(shè)，在圖1中，存在著4個網(wǎng)頁的拓補(bǔ)結(jié)構(gòu)，其中網(wǎng)頁D在指向網(wǎng)頁A的同時又指向了其他兩個網(wǎng)頁。其中網(wǎng)頁A的PR值如公式 （1）所示：

若用有向圖G (V,E)表示萬維網(wǎng)的話，那么V代表網(wǎng)頁集，E代表超鏈接集。其中網(wǎng)頁i的權(quán)威值可用公式（2）所示：

公式（2）中，P(i)代表網(wǎng)頁i的權(quán)威值，O(j)表示網(wǎng)頁j的鏈出鏈接總數(shù)，（i,j）代表網(wǎng)頁j指向網(wǎng)頁i的鏈接。根據(jù)萬維網(wǎng)中存在著懸垂葉等特征，Google最終將PageRank的計(jì)算公式確定為公式（3）所示：

公式（3）中，P代表網(wǎng)頁的權(quán)威向量，d代表阻尼系數(shù)，e代表單位矩陣，B是網(wǎng)頁的鏈接關(guān)系得到的轉(zhuǎn)移矩陣。

3 基于PageRank和最短路徑的用戶影響力評估算法

萬維網(wǎng)由大量的網(wǎng)頁和鏈接組成，微博由大量的用戶和關(guān)注關(guān)系組成，都可以用有向圖表示，所以，用戶影響力的評估可以借鑒PageRank算法。微博和萬維網(wǎng)的拓?fù)浣Y(jié)構(gòu)有所相似，也有所不同，網(wǎng)頁之間除了鏈接關(guān)系，其他的關(guān)系幾乎不存在，微博用戶之間除了關(guān)注關(guān)系，還存在著轉(zhuǎn)發(fā)微博、提及、評論等諸多行為關(guān)系，所以，在衡量微博用戶影響力的同時，應(yīng)考慮微博用戶行為這一核心要素。

3.1 微博網(wǎng)絡(luò)加權(quán)圖的構(gòu)成

用有向圖G (V,E)表示微博網(wǎng)絡(luò)，V代表用戶集，E代表關(guān)注關(guān)系集。關(guān)注關(guān)系涉及到評論X、轉(zhuǎn)發(fā)、提及等多種用戶行為，所以關(guān)注關(guān)系有著強(qiáng)弱之分，如圖2所示。

圖2 用戶關(guān)注網(wǎng)絡(luò)

圖2中的微博用戶關(guān)注網(wǎng)絡(luò)中，若用戶C同時關(guān)注了用戶E和用戶D，但是用戶C對用戶D的微博很少轉(zhuǎn)發(fā)、評論或者收藏，而對用戶E的微博卻是頻繁的轉(zhuǎn)發(fā)、評論等。本文在借鑒PageRank衡量用戶影響力時，會根據(jù)關(guān)注關(guān)系的強(qiáng)弱將C的影響力權(quán)值多分給用戶E，而少分給用戶D。

微博用戶之間的行為主要有評論、轉(zhuǎn)發(fā)、提及。這3種行為對于關(guān)注關(guān)系的強(qiáng)弱又有著不同程度的影響，從對微博消息傳播力度的角度考慮，轉(zhuǎn)發(fā)對關(guān)系的強(qiáng)度影響最大，提及其次，評論最小。本文采用加權(quán)融合的方法量化用戶之間的關(guān)注關(guān)系，并用關(guān)注度表示，如圖3所示。

圖3 用戶之間的關(guān)注度

根據(jù)圖3可知，用戶之間關(guān)注度的大小可由公式（4）表示：

在公式（4）中，A(u,v)代表用戶u和v之間的關(guān)注度，R代表用戶u轉(zhuǎn)發(fā)v的微博數(shù)，M代表用戶u評論v微博的總次數(shù)，@代表u提及v的總次數(shù)，用戶的關(guān)注度具有方向性。α，β，γ表示相應(yīng)因素的權(quán)值。由于微博用戶實(shí)際中的評論、轉(zhuǎn)發(fā)和提及都不是在一個數(shù)量級，若直接進(jìn)行加權(quán)計(jì)算，會面臨著大數(shù)吃小數(shù)的問題，所以要對每種行為數(shù)值進(jìn)行歸一化處理。本文采用離差標(biāo)準(zhǔn)化對這些行為數(shù)據(jù)進(jìn)行線性變換，如公式（5）所示：

在公式（5）中 Yi是歸一后的用戶轉(zhuǎn)發(fā)值（評論值，提及值），Xi是歸一前的用戶轉(zhuǎn)發(fā)微博數(shù)值（評論值，提及值），mini是用戶i在轉(zhuǎn)發(fā)（評論，提及）所有微博對象中，轉(zhuǎn)發(fā)值（評論值，提及值）最小的那個，同理maxi代表其最大的用戶轉(zhuǎn)發(fā)值（評論值，提及值）。在經(jīng)過歸一化處理之后，用戶之間的關(guān)注度可由公式（6）表示：

在公式（6）中A(U,V)‘代表經(jīng)過歸一化處理之后的用戶關(guān)注度，R’代表經(jīng)過歸一化處理之后的轉(zhuǎn)發(fā)數(shù)，M’代表經(jīng)過歸一化處理之后的評論數(shù)，@’代表經(jīng)過歸一化處理之后的提及數(shù)。在微博關(guān)注網(wǎng)絡(luò)圖中，加上用戶之間的關(guān)注度，可得到微博網(wǎng)絡(luò)加權(quán)圖。

3.2 權(quán)值分配計(jì)算

通過兩個用戶之間的關(guān)注度可以衡量用戶傳播消息的局部能力，卻不能從全局的角度衡量用戶傳播消息的能力。本文根據(jù)用戶在微博網(wǎng)絡(luò)中所處的關(guān)鍵位置，從全局的角度衡量用戶傳播消息的能力。

時效性是研究微博輿情的一個主要觀測點(diǎn)，在微博網(wǎng)絡(luò)中，用戶能否以最快的方式將消息傳播出去是衡量用戶影響力的關(guān)鍵因素。在微博網(wǎng)絡(luò)加權(quán)圖的基礎(chǔ)之上，通過用戶處于其他用戶到自己粉絲的最短路徑上的頻率衡量用戶的全局影響力，如圖4。

圖4 微博網(wǎng)絡(luò)加權(quán)圖

在圖4中，箭頭表示消息的走向，箭頭上的數(shù)值表示關(guān)系權(quán)值。為了計(jì)算的方便，將用戶之間的關(guān)注度進(jìn)行取逆運(yùn)算得到用戶之間的關(guān)系權(quán)值，即關(guān)系權(quán)值越小，關(guān)系越強(qiáng)。

圖4中，若A想要獲取D的微博消息，根據(jù)Floyd算法可知，消息最快的傳播路徑應(yīng)是D-＞B-＞A，而不是D-＞C-＞A，盡管A對C的關(guān)注關(guān)系很強(qiáng)，但是B對D的關(guān)注關(guān)系更強(qiáng)，消息的走向不僅依賴于A的關(guān)注關(guān)系，也依賴于B的關(guān)注關(guān)系。同樣，根據(jù)Floyd算法可知B、D、E、F、G用戶的微博消息若想以最快的方式流向A，都經(jīng)過B，說明B對A的影響力比C對A的影響力更強(qiáng)。

通過以上分析可知，一個用戶處于其他用戶之間最短路徑上的頻率越大，該用戶對微博消息的傳播作用力更強(qiáng)。例如在圖4中，所有節(jié)點(diǎn)到節(jié)點(diǎn)A的最短路徑中，通過B的有5次，通過C的有1次，那么A則將自己的影響力均分為6份，5份給B，1份給C。

3.3 算法核心

根據(jù)文中3.1和3.2的描述，在PageRank算法的基礎(chǔ)上，本文的算法核心基本上有以下3點(diǎn)：①粉絲數(shù)決定用戶影響力。②關(guān)注度決定用戶影響力。③位置決定用戶影響力。

本文UIA-PSP算法的核心可用公式（7）表示：

在公式（7）中，參照PageRank的公式，可知UIA-PSP（v）為v的用戶影響力，e為單位矩陣，F(xiàn)為根據(jù)用戶的關(guān)注關(guān)系和Floyd得到的轉(zhuǎn)移矩陣，即F（u,v）代表粉絲u貢獻(xiàn)給用戶v的比例值。其中F（u,v）可通過公式（8）確定：

在公式（8）中，t(i,v,u)表示微博網(wǎng)絡(luò)中其他任意節(jié)點(diǎn)i經(jīng)過用戶V達(dá)到用戶u的最短路徑數(shù)目，t(i,u)表示微博網(wǎng)絡(luò)中其他任意節(jié)點(diǎn)i到用戶u的最短路徑數(shù)目。

因此，UIA-PSP算法的核心結(jié)構(gòu)可如圖5所示。

綜上所述，UIA-PSP算法的核心可用如下偽代碼所示：

本算法中，根據(jù)Google給出參數(shù)建議，將阻尼因子d取值為0.85，ε取值為0.00001。根據(jù)層次分析法（AHP）可確定UIA-PSP算法中的參數(shù)為：α= 0.65A，β=0.0638，γ=0.2746[12]。

4 實(shí)驗(yàn)及結(jié)果分析

本文的實(shí)驗(yàn)數(shù)據(jù)是在數(shù)據(jù)堂提供的原始信息之上，利用微博爬蟲得到用戶之間的行為信息，主要的信息包含2012年1月1日至2016年1月1日的關(guān)注關(guān)系、轉(zhuǎn)發(fā)數(shù)目、評論數(shù)目、提及數(shù)目。最終得到的實(shí)驗(yàn)數(shù)據(jù)包含114名用戶，703條關(guān)注關(guān)系。部分實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

圖6 實(shí)驗(yàn)的部分?jǐn)?shù)據(jù)

為了進(jìn)行實(shí)驗(yàn)的對比分析，本文采用PageRank算法和基于用戶的粉絲數(shù)衡量用戶影響力的算法（User Influence Assessment Based on the number of User’ Fans，UIA-UF）作為UIA-PSP算法的兩種對比算法，進(jìn)行綜合的分析比較。

采用UIA-PSP對用戶影響力進(jìn)行排序，排序結(jié)果如圖7所示。

圖7 UIA-PSP排序結(jié)果

采用PageRank對用戶影響力進(jìn)行排序，排序結(jié)果如圖8所示。

采用UIA-UF對用戶影響力進(jìn)行排序，排序結(jié)果如圖9所示。

本文采用P@N作為實(shí)驗(yàn)分析指標(biāo)，衡量UIAPSP算法的準(zhǔn)確性，P@N的計(jì)算公式，如公式（9）所示：

在公式（9）中，AN∩BN代表算法A（B）得到的前N名用戶影響力的交集量，本文N的取值分別為10、20、30、40、50、60、70、80。

圖8 PageRank排序結(jié)果

圖9 UIA-UF排序結(jié)果

若將以UIA-UF為基線模型，以PageRank和UIAPSP為對比模型，那么對比模型所得結(jié)果在P@N指標(biāo)下的表現(xiàn)如表1所示。

表1 以UIA-UF為基線算法的P@N值測試結(jié)果

若以PageRank為基線模型，以UIA-UF和本文的UIA-PSP算法為對比模型，那么對比模型所得結(jié)果在P@N指標(biāo)下的表現(xiàn)如表2所示。

表2 以PageRank為基線算法的P@N值測試結(jié)果

從表1和表2中，通過UIA-PSP得到用戶影響力排名結(jié)果的準(zhǔn)確率與N值成正比例。在表1中，以UIA-UF為基線模型時，PageRank得到結(jié)果的準(zhǔn)確率高于UIA-PSP，并且幅度從0～50%不等，這說明UIA-PSP相比PageRank對用戶影響力的排名進(jìn)行了調(diào)整。在表2中，以PageRank為基線算法時，UIA-PSP得到結(jié)果的準(zhǔn)確率總體上高于UIA-UF，并且幅度從0-30%不等。這可以得出兩個結(jié)論：①PageRank與UIA-UF更為相似。②UIA-PSP與兩個算法對比都各有不同。

在UIA-PSP中，粉絲最多的27號用戶僅排名23位，在PageRank中排名28位，這說明了在UIA-PSP算法中，粉絲僅是衡量用戶影響力的一個因素，但不是決定性因素。在PageRank算法中排名第一的57號用戶，在UIA-PSP算法中排名第56位，因?yàn)?7號用戶擁有大量的粉絲，而且其中有3個粉絲的用戶影響力很大，所以PageRank得到的57號用戶影響力就很大；在UIA-PSP中，其他用戶之間的最短路徑中經(jīng)過57號用戶的數(shù)量很少，所以排名有所下滑。類似的用戶還有21、86號用戶。在UIAPSP得到的用戶影響力排名結(jié)果中，22號用戶排名第一，因?yàn)橥ㄟ^22號用戶的最短路徑多達(dá)312條，也是因?yàn)?2號用戶的部分粉絲影響力很大，所以22號用戶獲得了較多的用戶影響力貢獻(xiàn)值。類似的用戶還有11、81號用戶等。這可得出第3個結(jié)論：UIA-PSP算法能夠通過用戶處傳播消息的能力衡量用戶的影響力。

通過實(shí)驗(yàn)可知，UIA-PSP算法根據(jù)用戶關(guān)注度衡量用戶的局部影響力，又根據(jù)用戶處于其他用戶之間的最短路徑上的頻率衡量用戶的全局影響力。在公安工作中，可將此算法作為參考，進(jìn)行輿情的實(shí)時管控。例如在微博網(wǎng)絡(luò)中，可通過用戶的關(guān)注度找出那些粉絲真正關(guān)注的用戶，也可通過用戶處于其他用戶之間的最短路徑上的頻率找出推動微博消息快速傳播的用戶。在出現(xiàn)微博輿情時，可實(shí)現(xiàn)對重點(diǎn)人員和幕后推動輿情發(fā)展人員的實(shí)時監(jiān)控，而不是對那些僅僅擁有眾多粉絲數(shù)的“大V”進(jìn)行盲目的監(jiān)控。另外通過本算法，可提取出微博輿情傳播的主體框架，對輿情的下一步發(fā)展以及輿情的導(dǎo)控做出科學(xué)的判斷。

5 小結(jié)

本文在PageRank和最短路徑的基礎(chǔ)上提出了UIA-PSP算法，既根據(jù)用戶行為考慮到了用戶的局部影響力，又根據(jù)用戶在微博中的位置考慮了用戶的全局影響力。實(shí)驗(yàn)結(jié)果證明了UIA-PSP具有較高的說服力。

參考文獻(xiàn)：

[1] 張坤.國內(nèi)微博的傳播形態(tài)與發(fā)展研究[D].南昌:江西師范大學(xué),2012:6-15.

[2] Maksim Tsvetovat,Alexander Kouznetsov.社會網(wǎng)絡(luò)分析方法與實(shí)踐[M].王薇,王成軍,王穎,等譯.北京:機(jī)械工業(yè)出版社,2013:13-45.

[3] 王彪.社交網(wǎng)絡(luò)中的用戶影響力分析[D].哈爾濱:哈爾濱工業(yè)大學(xué),2012:4-19.

[4] 陳少欽.基于PageRank的社交網(wǎng)絡(luò)用戶實(shí)時影響力研究[D].上海:上海交通大學(xué),2013:12-33.

[5] 肖宇.校園網(wǎng)絡(luò)信息傳播特性與用戶影響力研究[D].武漢:華中科技大學(xué),2012:8-55.

[6] 齊超,陳鴻昶,于洪濤.基于用戶行為綜合分析的微博用戶影響力評價方法[J]. 計(jì)算機(jī)應(yīng)用研究,2014(7):2004-2007.

[7] 朱郭峰,楊彥,周竹榮,等.基于領(lǐng)域的微博用戶影響力計(jì)算方法[J].西南大學(xué)學(xué)報(bào)(自然科學(xué)版)2014(3):145-151.

[8] Ye S,Wu S F.Measuring Message Propagation and Social Influence on Twitter.com[J]．International Journal of Communication Networks & Distributed Systems,2010(1):216-231.

[9] 郭浩,陸玉良,王宇,等.基于信息傳播的微博用戶影響力度量[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),2012(5):78-83.

[10] 陳燦.微博用戶的影響力分析[D].濟(jì)南:山東大學(xué),2013:16-33.

[11] 劉兵.Web數(shù)據(jù)挖掘[M].北京:清華大學(xué)出版社,2009:66-99.

[12] 郭金玉,張忠彬,孫慶云.層次分析法的研究與應(yīng)用[J].中國安全科學(xué)學(xué)報(bào),2008(5):148-153.