考慮用戶和傳播屬性的節點影響力評估算法*

尚 焱,樊欣唯，于 洪

(北京郵電大學信息物理融合實驗室，北京 100876)

考慮用戶和傳播屬性的節點影響力評估算法*

尚 焱,樊欣唯，于 洪

(北京郵電大學信息物理融合實驗室，北京 100876)

在微博的傳播過程中，關鍵節點起著意見領袖的作用，在社交網絡中發現關鍵節點對輿情的分析、控制等方面是非常有意義的，作為社交網絡的傳播節點，用戶不僅與用戶本身屬性有關，還與微博消息的傳播屬性有關。對兩種屬性分別選取三個指標，利用層次分析法中構造判斷矩陣的方法評估各個指標的權重，將用戶系數和傳播系數分別作為傳播網絡的節點和邊的權值，形成雙加權的網絡拓撲圖，然后建立考慮用戶和傳播屬性的影響力評估算法來計算轉發節點的影響力。通過與現有算法進行比較，表明本文的算法能夠更加客觀準確地評估關鍵節點在傳播過程中的重要程度。

關鍵節點；用戶系數；傳播系數；層次分析法；NodeRank算法

1 引言

微博是一種通過關注機制[1]分享簡短實時信息的廣播式的社交網絡平臺，由于其自身的社交模式，決定了微博信息的傳播是爆炸式的，而在傳播過程中關鍵節點[2]是傳播影響力的決定因素，合理客觀地評估關鍵節點的影響力在控制消息的傳播、輿論形勢分析等方面具有重大的意義。微博的消息傳播是通過產生轉發關系進行的，整個傳播過程可以抽象為網絡拓撲圖[3]，該圖的節點是轉發用戶，圖的邊表示轉發關系，在整個拓撲結構中，通過相應算法進行節點影響力評估，從而發現傳播過程中的關鍵節點，為進一步進行輿情的分析與控制提供線索。

現階段評估網絡拓撲圖中重要節點的方法有很多，其中大多數方法都是將傳播過程抽象為網絡拓撲結構，基于節點的度[4]、統計分析方法[5]、互信息的方法[6]以及Google的PageRank網頁排名算法[7]。這些經典的算法都可以在不同維度上評估節點的重要程度，但是依然各有其局限性，由于評價指標單一，并沒有真正考慮更加豐富的用戶信息和傳播過程中的因素，并不具備較高的客觀性和真實性。其中PageRank算法在衡量關鍵節點具有獨特的優勢，該算法用于衡量特定網頁相對于搜索引擎索引中的其他網頁而言的重要程度，這和微博傳播中的節點關系相類似。基于此思想構建了考慮用戶和傳播屬性的節點影響力評估模型并提出了NodeRank算法，然后將微博的傳播過程抽象為網絡拓撲圖，在真實的微博傳播過程中，由于轉發用戶的屬性和微博傳播的屬性存在差異，產生不同的影響效果。因此，微博的傳播網絡應該是一個節點和邊都具有權值的加權傳播網絡，利用本文的NodeRank算法計算關鍵節點影響力，然后結合微博可視化工具，將實驗結果與現有的算法結果進行對比，表明NodeRank算法可以更加準確合理地評估關鍵節點的影響力。

2 評估模型

用戶屬性和傳播屬性對微博的傳播存在著不同的影響效果，消息傳播屬性更加依賴于微博的內容，用戶屬性則更加依賴用戶本身的某些特性。本文中用戶系數表示用戶的屬性，傳播系數表示微博傳播過程的屬性，然后基于多目標決策的思想計算用戶屬性的系數和傳播屬性的系數，將網絡傳播拓撲圖的節點和邊分別賦予用戶系數和傳播系數，從而變為加權網絡，然后通過NodeRank算法進行關鍵節點的挖掘與評估。用戶自身屬性包括是否通過V認證、粉絲量、好友數、評論量和轉發量等特征，在消息傳播過程中，不同屬性的用戶具有不同的影響力。本文選擇活躍度[8]、關系強度[9]和權威系數作為衡量傳播屬性的指標，計算出用戶系數作為傳播網絡節點的權值。微博傳播過程中，由于傳播過程的某些因素存在差異，比如用戶的偏好[10]、爆炸性內容等造成不同類型的微博傳播速度、互動程度[11]和轉發層級不同，從而造成傳播過程的差異。本文選擇轉發速度、傳播深度和交互指數作為衡量傳播屬性的指標，計算傳播系數作為傳播拓撲網絡邊上的權值。

2.1 用戶屬性指標

2.1.1 活躍度

微博用戶相同時間內發布的微博數越多，說明該用戶活躍程度越高，相比其他用戶該用戶的影響力越強，將用戶平均每天發布的微博數目定義為用戶的活躍度，用來衡量用戶的活躍程度，記為A(Activeness)。

(1)

其中，WC(Weibo Counts)為用戶已發布的微博數,t1為用戶注冊時間,t2為微博發布時間。

2.1.2 關系強度

基于效用函數思想，將用戶的好友數與粉絲數的比值取負對數變換定義為關系強度，記為RI(Relation Intensity)。該指標衡量用戶的社交屬性，當該值大于0時，用戶與其他人之間呈現一種弱關系，該用戶更加趨向于自媒體特性，具有自媒體特性的用戶大都是信息的生產者，影響力相對較大；相反，該值小于0時，說明該用戶與其粉絲呈現“強關系”，也就意味著該用戶在真實生活里相識的概率更大，與其他用戶之間在線下具有真實的社交關系，這種用戶更加趨向于社交特性，大都是信息的消費者，其影響力也就相對較小。

(2)

其中,FLC(Follower Counts)為用戶粉絲數,FRC(FRiends Counts)為用戶好友數。

2.1.3 權威系數

用戶是否經過認證對其影響力有著顯著的影響。通常來講，認證用戶更容易贏得其他用戶的信任，其影響力顯然比普通用戶要大。通過統計認證用戶的關系強度，發現大多數認證用戶趨向于“弱關系”，也就是說，認證用戶大多趨向自媒體特性，這與微博的認證條件相符合。用戶認證條件是有一定知名度的演藝、體育、文藝界人士、在公眾熟悉的某領域內有一定知名度和影響力的人、知名企業、機構、媒體及其高管，或者重要新聞當事人。通過認證的用戶其影響力普遍高于普通用戶，將認證用戶與普通用戶賦予不同的系數。是否通過認證定義為權威系數，記為AI(Authority Indicator )。

(3)

2.2 傳播屬性指標

2.2.1 轉發速度

微博的傳播依靠的是與其他用戶產生轉發關系，當產生轉發關系時，微博消息才會傳向下一級網絡，才會對下一級用戶產生影響。如果某微博消息傳播速度越大，即單位時間內產生的轉發關系越多，說明其影響力也越大。將單位時間內轉發關系產生的個數定義為轉發速度，記為RV(Report Velocity)。

(4)

其中,t為微博傳播時間，CN(Comment Number)為微博評論量。

2.2.2 傳播深度

微博消息被連續轉發的次數越多，說明該微博的傳播層級越大，傳播層級越大說明該條微博傳播深度越深，影響程度也越大，這里所講的傳播層級并不是任意一個用戶轉發次數，而是轉發用戶相對于原微博經歷的連續轉發次數，將所有轉發用戶中的最大連續轉發次數定義為絕對傳播深度。將某用戶所處的傳播層級與絕對傳播深度的比值定義為相對傳播深度，記為PD(Propagation Depth)。

(5)

其中,Lmax表示傳播過程中的絕對傳播深度，Li表示第i個用戶相對于原微博所在的轉發層級。

2.2.3 交互指數

微博的評論數或者轉發數可以說明該微博的受關注程度，同時也說明該微博內容更符合某些用戶的偏好。另一方面，具有自媒體特性的用戶和具有社交屬性的用戶由于被關注量和好友數的不同產生的交互程度存在差異，該指標又與用戶的關系強度有關。將交互指數定義為總的轉發評論量與該用戶好友數的比值，記為IC(Interaction Coefficient)。

(6)

其中,CN(Comment Number)為微博評論量,FRN為用戶的好友數。

2.3 用戶和傳播影響系數

在微博節點的影響力評估過程中，對兩種影響系數分別選擇三個屬性，為了確定用戶屬性和傳播屬性的權值，采用多目標決策分析法的思想，將三個評價指標合成為一個權值，并對每個指標數據進行歸一化處理，使得兩個權值落在相同的區間內。這種處理方法并不影響數據之間的相關性，能夠保證原始數據的真實情況。通過分析得知，各個指標之間具有相關性，并且互相不可替代，適合用加法規則綜合評定。為了使得屬性權值更加準確，采用層次分析法[12]中構建判斷矩陣的方法來評估各個指標的權重。構建用戶屬性和傳播屬性的判斷矩陣分別記為A和B。

經過Matlab編程計算得到，用戶屬性的活躍度、關系強度、權威系數的權重分別為0.070 2、0.370 7、0.559 0，傳播屬性的傳播速度、傳播深度、交互指數的權重分別為0.671 6、0.265 4、0.062 9。將用戶系數和傳播系數分別定義為U和V，計算公式如下：

U=0.0702A+0.3707RI+0.5590AI

(7)

其中，U為加權網絡拓撲圖中的節點權值；A、RI、AI分別為公式(1)～公式(3)確定的用戶屬性的指標數值。

V=0.6716RV+0.2654PD+0.0629IC

(8)

其中，V為加權網絡拓撲圖中的邊的權值；RV、PD、IC分別為公式(4)～公式(6)確定的傳播屬性的指標數值。

3 NodeRank算法

3.1 算法思想

基于PageRank的算法思想，提出考慮用戶和傳播屬性的節點影響力評估算法，本模型的基本思想是：將節點的轉發概率作為阻尼系數[13]，用來表征消息的傳播概率[14]。同時，將用戶系數和未轉發概率的乘積值平均分配給未轉發的用戶，即未轉發情況下，將節點的用戶影響力平均分配給每個可能轉發的關注者。在轉發情況下，節點的所有轉發用戶的影響力和傳播系數加權之后再求和，即邊權乘上產生轉發關系的用戶影響力之和。該算法刻畫出了轉發過程中用戶之間的轉發關系，并且考慮了用戶特性和傳播狀況，更加準確客觀地評估了傳播過程中節點的真實情況，同時反映了轉發關系的重要性，體現了用戶屬性的影響程度，更加全面真實地評估了關鍵節點的影響力。

(9)

其中，P(i)是第i個節點的轉發概率，公式如下：

(10)

以上兩式中：ni為節點i的轉發量，N為總的轉發量，I(i)是第i個節點的綜合影響力，I(j)是第j個轉發節點的綜合影響力，Ni是第i個節點的粉絲數，Sj是轉發該用戶微博的用戶集合。

由式(7)得，Ui是第i節點的用戶系數；由式(8)得，Vij是第i節點到第j節點的傳播系數。

3.2 算法實現

根據用戶和傳播屬性評估模型，得到用戶系數和傳播系數，也就得到了拓撲傳播網絡中節點的權值和邊的權值。設加權傳播網絡為圖G=(M，N)， 其中，M是所有節點的集合，即轉發用戶的集合；N是所有邊的集合，即轉發關系的集合，每一條邊代表一次轉發關系。根據加權之后的網絡傳播圖，利用微博工具所提供的原始數據，將NodeRank算法代入進行關鍵節點的挖掘和評估。

Step 1 將采集到的數據帶入用戶和傳播屬性評估模型，得到六個指標的計算數值；

Step 2 利用Min-Max 標準化方法對六個指標的原始數據進行標準化處理，并利用層次分析法中構建判斷矩陣的方法計算各個指標權重；

Step 3 將用戶屬性和傳播屬性的三個指標分別代入式(7)和式(8)得到用戶影響系數和傳播影響系數；

Step 4 構建加權傳播網絡圖G=(V，U)，得到轉發關系；

Step 5 通過式(10)各個節點的轉發關系計算第i個節點的轉發概率P(i)；

Step 6 將以上得到的指標數值代入NodeRank算法公式(9)計算各個用戶的影響力；

第一，要立足于“我國是工人階級領導的，以工農聯盟為基礎的人民民主專政的社會主義國家”的國家性質上，堅持“人民是國家的主人”原則，始終站在人民群眾（即思想政治教育的受教育者）的根本立場上，做合乎民族的、符合人民群眾的根本利益的思想政治教育工作。

Step 7 根據計算出的各個用戶的影響力從大到小排序，得到最終影響力排序。

由以上步驟得知，該算法的復雜度主要集中在Step 6，雖然基于PageRank算法大大降低了計算的復雜度，但是對于微博這種實時的傳播事件還要求進一步提高算法的效率，下一步的研究方向偏向于這方面內容。

4 實驗結果

4.1 數據來源

WeiboEvents[15]是北京大學可視化與可視分析研究組開發的微博傳播分析工具，通過直觀的視圖清晰地呈現出一個事件中微博轉發的過程，能夠迅速地發現事件中的關鍵人物、關鍵微博、重要觀點，同時通過可視化的方式幫助更好地分析微博中事件的發生與發展過程，并可以下載文中各指標的原始數據。利用WeiboEvents，將原創微博的URL輸入到該工具中，通過后臺的采集得到原始數據，并通過可視化分析為下一步的算法分析奠定基礎。

4.2 數據預處理

利用Min-Max 標準化方法對六個指標的原始數據進行標準化處理，消除不同指標數據之間因量綱不同帶來的數值級數上的影響，并且Min-Max標準化方法保留了原始數據之間的相關關系。Min-Max標準化方法是對原始數據進行線性變換。具體算法如下：

設Xmin和Xmax分別為某種屬性的最小值和最大值，將屬性的一個原始值X通過Min-Max標準化映射成在區間[0，1]的值X′，其公式為：

4.3 計算結果及可視化分析

通過對原始數據的處理和模型的計算結果，將結果代入到本文的影響力評估算法中，計算得到七個影響力較大的關鍵節點，這七個節點的用戶系數、傳播系數、節點的轉發概率以及最終的影響力和排序結果如表1所示。

Table 1 Results of the NodeRank algorithm

由表1可得，“21世紀經濟報道”具有最大的影響力，這與圖1的可視化結果相符合，這也不難解釋，因為該用戶是原創微博，屬于內容的生產者，所以影響力最大。由于該微博經過“李開復”的轉發形成二次較大的爆發，其引起的轉發量比原創微博還要略高，但由于其傳播影響系數較低，使得綜合影響力并不突出，“薛蠻子”影響力排第三，該結果與圖1和圖2的可視化結果完全一致。由圖1和圖2所示，“洪晃ilook”具有第四影響力，但結果卻排在“李佳佳Audrey”之后，原因是李佳佳節點是引起微博二次爆發至關重要的連接節點，正是由此節點之后的轉發才引起了大規模的二次爆發，而在“薛蠻子”之后爆發規模并不大，所以該節點應比“薛蠻子”更重要，即若沒有此節點，就沒有該微博消息的第二次較大規模的爆發。

Figure 1 Hierarchy chart of a broadcast tree圖1 樹狀轉發層次圖

Figure 2 Topological graph of Weibo spread圖2 微博傳播網絡拓撲圖

對比發現，“李佳佳Audrey”的用戶影響系數和傳播影響系數均為最低，說明本文的算法可以挖掘關鍵節點。用戶“朱駿”的用戶影響系數比“21世紀經濟報道”要高，但由于其傳播影響系數與其相差懸殊，導致“朱俊”影響力并不大。用戶“環保董良杰”的轉發量比用戶“洪晃ilook”要大，但是其用戶影響系數和傳播影響系數都比“洪晃ilook”小，導致其綜合影響力偏小。通過對各個用戶的對比分析表明，本文的算法可以更加準確、合理、客觀地評估用戶影響力，其排序結果與可視化結果一致，并且可以挖掘關鍵節點，計算結果可以作為輿情分析等工作的參考。

4.4 不同算法的對比分析

在理論介紹部分，已經介紹了幾種經典的評估節點重要程度的算法，這些算法都從不同角度進行影響力評估。我們選擇基于節點的度、互信息算法和PageRank算法三種經典算法與NodeRank算法進行對比，通過Matlab編程和Excel數據處理最終得到三個對比算法的計算結果，如表2所示，對三種算法的計算結果進行排序得到最終影響力的排名，如表3所示。

Table 2 Computational results of different algorithms

通過與基于節點的度和互信息算法的對比，我們發現：兩種對比算法都將用戶“李佳佳Audrey”排在最后，通過分析可知，該用戶是連接兩次大規模爆發的關鍵節點，重要程度明顯不小，說明本文算法更加合理。進一步與基于互信息的算法對比，當除去用戶“李佳佳Audrey”時，與本文算法計算

Table 3 Sorted results of different algorithms

結果完全一致，說明兩種算法在計算爆發量比較大的用戶影響力時，準確性是相當的，而基于互信息的算法對于爆發量相對較小的重要節點的挖掘不夠準確。

通過與傳統的PageRank算法對比發現：傳統的PageRank算法認為用戶“李佳佳Audrey”是最重要的，說明該算法在發現關鍵節點上具有良好的準確性，但該結果有失客觀性，該用戶為關鍵節點但并不比爆發量較大用戶更具影響力。對比發現，基于NodeRank算法更勝一籌，基于節點的度和互信息算法并不可以發現用戶“李佳佳Audrey”的重要性，將其排在最后，PageRank算法又低估了爆發節點的影響力，而NodeRank算法既可以發現關鍵節點又準確地評估了爆發節點，說明本文的算法更具有客觀性、合理性和準確性。

5 結束語

本文基于PageRank算法思想，提出了一種考慮用戶和傳播屬性的節點影響力評估算法——NodeRank算法。利用微博分析工具進行數據采集和可視化分析，將傳播網絡抽象為雙加權拓撲網絡，根據WeiboEvents所提供的原始數據，將算法代入，對傳播過程中的關鍵節點進行挖掘和評估。通過與現有三種經典算法的實驗對比，NodeRank算法具有較好的準確性，能夠發現至關重要的關鍵節點和極具影響力的爆發節點，并客觀地評估其重要程度。對于實時的微博事件，計算的復雜度還有待提高，降低計算復雜度以便快速高效地挖掘關鍵節點，將是下一步研究的重點。

[1] Wang Xiao-yun.Research on the mechanism of following-based topics of microblogging social network [D]. Wuhan:Huazhong University of Science &Technology,2013.(in Chinese)

[2] Sahelices-Pinto C,Rodríguez-Santos C. E-WoM and 20 opinion leaders[J].Journal of Food Products Marketing,2014,20(3):244-261.

[3] Zhao Ying,Yi Ping-ke.A dynamic worm propagation model based on social network [J].Computer Engineering & Science,2013,35(12):34-38.(in Chinese)

[4] Qiu Jun,Liu Gong-shen. A relationship-based importance algorithm for micro-blog network system [J]. Information Security and Communications Privacy,2013,1(1):51-53.(in Chinese)

[5] Yu Hong,Yang Xian. Information propagation on microblogging using statistical analysis technique [J]. Digital Communication,2013,40(2):6-10.(in Chinese)

[6] Zhang Yi,Liu Yu-hua,Xu Kai-hua,et al. Evaluation method for node importance based on mutual information in complex networks [J]. Computer Science,2013,38(6):88-109.(in Chinese)

[7] Li Xing,Zhong Zhi-nong,Jing Ning,et al.Reaserch on community detection method [J]. Computer Engineering & Science,2012,34(9):154-159.(in Chinese)

[8] Wang Chen-xu,Guan Xiao-hong,Qin Tao,et al.Who are active? An in-depth measurement on user activity characteristics in Sina microblogging[C]∥Proc of Global Communications Conference (GLOBECOM),2012:2083-2088.

[9] Han Zhong-ming,Yuan Li-ling,Yang Wei-jie,et al. Algorithm for discovering influential nodes in weighted social networks [J]. Computer Applications,2013,33(6):1553-1557.(in Chinese)

[10] Kandiah V,Shepelyansky D L.PageRank model of opinion formation on social networks[J].Physica A:Statistical Mechanics and its Applications,2012,391(22):5779-5793.

[11] Li Xiang,Cheng Shao-yin,Chen Wen-long,et al. Novel user influence measurement based on user interaction in microblog[C]∥Proc of 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2013:615-619.

[12] Liu Xin-xian，Zhu Dao-li. Selection and judgment:AHP [M]. Shanghai:Shanghai Science Popularization Press,1990.(in Chinese)

[13] Chen Wen-long,Cheng Shao-yin,He Xing.InfluenceRank:An efficient social influence measurement for millions of users in microblog [C]∥Proc of the 2nd International Conference on Cloud and Green Computing / 2nd International Conference on Social Computing and its Applications,2012:563-570.

[14] Wang Jin-hui，He Li-jian，Zhang Wei，et al. Research of user preference based information dissemination in microblog [J]. Computer Engineering & Science,2013,35(3):140-144.(in Chinese)

[15] Ren Dong-hao,Xin Zhang,Wang Zhen-huang,et al. WeiboEvents:A crowd sourcing Weibo visual analytic system[C]∥Proc of 2014 IEEE Pacific Visualization Symposium (PacificVis) Notes,2014,:330-334.

附中文參考文獻:

[1] 王小云.基于主題的微博社會網絡關注機制研究[D]. 武漢:華中科技大學,2013.

[3] 趙英,易平科.基于社交網絡的蠕蟲動態傳播模型[J].計算機工程與科學,2013,35(12):34-38.

[4] 仇鈞,劉功申.基于關系的微博重要度算法研究[J].信息安全與通信保密,2013,1(1):51-53.

[5] 于洪,楊顯.基于統計分析的微博信息傳播規律研究[J].數字通信,2013,40(2):6-10.

[6] 張翼,劉玉華,許凱華,等.一種基于互信息的復雜網絡節點重要性評估方法[J].計算機科學,2013,38(6):88-109.

[7] 李星,鐘志農,景寧,等.社區挖掘技術研究[J].計算機工程與科學,2012,34(9):154-159.

[9] 韓忠明,苑麗玲,楊偉杰,等.加權社會網絡中重要節點發現算法[J].計算機應用,2013,33(6):1553-1557.

[12] 劉新憲，朱道立. 選擇與判斷：AHP[M].上海:上海科學普及出版社,1990.

[14] 王金輝，賀利堅，張偉，等.微博中基于用戶偏好的信息傳播研究[J].計算機工程與科學,2013,35(3):140-144.

尚焱(1990-),男,山東寧津人，碩士生，研究方向為Web 搜索和數據挖掘。E-mail:shang.yan@foxmail.com

SHANG Yan,born in 1990,MS candidate,his research interests include web search, and data mining.

樊欣唯(1992-),女,上海人，碩士生，研究方向為數據中心網絡路由策略。E-mail:20151202026t@cqu.edu.cn

FAN Xin-wei,born in 1992,MS candidate,her research interest includes routing policy of data center network.

于洪(1972-),女,重慶人，博士，副教授，CCF會員(E200010612M)，研究方向為數據挖掘、粗糙集理論和Web智能等。E-mail:yuhongcq@aliyun.com

YU Hong,born in 1972,PhD,associate professor,CCF member(E200010612M)，her research interests include data mining, rough set theory, and web intelligence.

A novel node influence measurement algorithm based on characteristics of users and propagation

SHANG Yan，FAN Xin-wei，YU Hong

(Laboratory of Cyber-Physical Systems,Beijing University of Posts and Telecommunications,Beijing 100876,China)

During the spreading process of microblogs, key nodes play an important role as “attitude leaders”. It is essential to figure out those key nodes for analyzing and monitoring public sentiments. As propagation nodes, users’ variety not only depends on their own characteristics, but also the characteristics of propagation. We select three indicators among two characteristics and adopt the evaluation array of the analytic hierarchy process to assess these indicators. User coefficient and propagation coefficient are used as the node weight and the edge weight respectively, thus forming a double weighted topological graph. Then we establish a novel node influence measurement algorithm of nodes based on the characteristics of users and propagation to evaluate the influence of each node. Compared with existing algorithms, the proposed algorithm can evaluate the importance of key nodes more accurately and objectively during propagation process.

key nodes;user coefficient;propagation coefficient;analytic hierarchy process;NodeRank algorithm;

1007-130X(2015)11-2105-07

2015-01-07;

2015-08-11

國家自然科學基金資助項目(61379114)

TP391

A

10.3969/j.issn.1007-130X.2015.11.017

通信地址：100876 北京市海淀區西土城路10號北京郵電大學信息物理融合實驗室教四

418Address:Laboratory of Cyber-Physical Systems，Beijing University of Posts and Telecommunications,Beijing 100876,P.R.Chin