尚 焱,樊欣唯，于 洪

(北京郵電大學(xué)信息物理融合實(shí)驗(yàn)室，北京 100876)

考慮用戶和傳播屬性的節(jié)點(diǎn)影響力評(píng)估算法*

尚 焱,樊欣唯，于 洪

(北京郵電大學(xué)信息物理融合實(shí)驗(yàn)室，北京 100876)

在微博的傳播過(guò)程中，關(guān)鍵節(jié)點(diǎn)起著意見(jiàn)領(lǐng)袖的作用，在社交網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)對(duì)輿情的分析、控制等方面是非常有意義的，作為社交網(wǎng)絡(luò)的傳播節(jié)點(diǎn)，用戶不僅與用戶本身屬性有關(guān)，還與微博消息的傳播屬性有關(guān)。對(duì)兩種屬性分別選取三個(gè)指標(biāo)，利用層次分析法中構(gòu)造判斷矩陣的方法評(píng)估各個(gè)指標(biāo)的權(quán)重，將用戶系數(shù)和傳播系數(shù)分別作為傳播網(wǎng)絡(luò)的節(jié)點(diǎn)和邊的權(quán)值，形成雙加權(quán)的網(wǎng)絡(luò)拓?fù)鋱D，然后建立考慮用戶和傳播屬性的影響力評(píng)估算法來(lái)計(jì)算轉(zhuǎn)發(fā)節(jié)點(diǎn)的影響力。通過(guò)與現(xiàn)有算法進(jìn)行比較，表明本文的算法能夠更加客觀準(zhǔn)確地評(píng)估關(guān)鍵節(jié)點(diǎn)在傳播過(guò)程中的重要程度。

關(guān)鍵節(jié)點(diǎn)；用戶系數(shù)；傳播系數(shù)；層次分析法；NodeRank算法

1 引言

微博是一種通過(guò)關(guān)注機(jī)制[1]分享簡(jiǎn)短實(shí)時(shí)信息的廣播式的社交網(wǎng)絡(luò)平臺(tái)，由于其自身的社交模式，決定了微博信息的傳播是爆炸式的，而在傳播過(guò)程中關(guān)鍵節(jié)點(diǎn)[2]是傳播影響力的決定因素，合理客觀地評(píng)估關(guān)鍵節(jié)點(diǎn)的影響力在控制消息的傳播、輿論形勢(shì)分析等方面具有重大的意義。微博的消息傳播是通過(guò)產(chǎn)生轉(zhuǎn)發(fā)關(guān)系進(jìn)行的，整個(gè)傳播過(guò)程可以抽象為網(wǎng)絡(luò)拓?fù)鋱D[3]，該圖的節(jié)點(diǎn)是轉(zhuǎn)發(fā)用戶，圖的邊表示轉(zhuǎn)發(fā)關(guān)系，在整個(gè)拓?fù)浣Y(jié)構(gòu)中，通過(guò)相應(yīng)算法進(jìn)行節(jié)點(diǎn)影響力評(píng)估，從而發(fā)現(xiàn)傳播過(guò)程中的關(guān)鍵節(jié)點(diǎn)，為進(jìn)一步進(jìn)行輿情的分析與控制提供線索。

現(xiàn)階段評(píng)估網(wǎng)絡(luò)拓?fù)鋱D中重要節(jié)點(diǎn)的方法有很多，其中大多數(shù)方法都是將傳播過(guò)程抽象為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，基于節(jié)點(diǎn)的度[4]、統(tǒng)計(jì)分析方法[5]、互信息的方法[6]以及Google的PageRank網(wǎng)頁(yè)排名算法[7]。這些經(jīng)典的算法都可以在不同維度上評(píng)估節(jié)點(diǎn)的重要程度，但是依然各有其局限性，由于評(píng)價(jià)指標(biāo)單一，并沒(méi)有真正考慮更加豐富的用戶信息和傳播過(guò)程中的因素，并不具備較高的客觀性和真實(shí)性。其中PageRank算法在衡量關(guān)鍵節(jié)點(diǎn)具有獨(dú)特的優(yōu)勢(shì)，該算法用于衡量特定網(wǎng)頁(yè)相對(duì)于搜索引擎索引中的其他網(wǎng)頁(yè)而言的重要程度，這和微博傳播中的節(jié)點(diǎn)關(guān)系相類似?；诖怂枷霕?gòu)建了考慮用戶和傳播屬性的節(jié)點(diǎn)影響力評(píng)估模型并提出了NodeRank算法，然后將微博的傳播過(guò)程抽象為網(wǎng)絡(luò)拓?fù)鋱D，在真實(shí)的微博傳播過(guò)程中，由于轉(zhuǎn)發(fā)用戶的屬性和微博傳播的屬性存在差異，產(chǎn)生不同的影響效果。因此，微博的傳播網(wǎng)絡(luò)應(yīng)該是一個(gè)節(jié)點(diǎn)和邊都具有權(quán)值的加權(quán)傳播網(wǎng)絡(luò)，利用本文的NodeRank算法計(jì)算關(guān)鍵節(jié)點(diǎn)影響力，然后結(jié)合微博可視化工具，將實(shí)驗(yàn)結(jié)果與現(xiàn)有的算法結(jié)果進(jìn)行對(duì)比，表明NodeRank算法可以更加準(zhǔn)確合理地評(píng)估關(guān)鍵節(jié)點(diǎn)的影響力。

2 評(píng)估模型

用戶屬性和傳播屬性對(duì)微博的傳播存在著不同的影響效果，消息傳播屬性更加依賴于微博的內(nèi)容，用戶屬性則更加依賴用戶本身的某些特性。本文中用戶系數(shù)表示用戶的屬性，傳播系數(shù)表示微博傳播過(guò)程的屬性，然后基于多目標(biāo)決策的思想計(jì)算用戶屬性的系數(shù)和傳播屬性的系數(shù)，將網(wǎng)絡(luò)傳播拓?fù)鋱D的節(jié)點(diǎn)和邊分別賦予用戶系數(shù)和傳播系數(shù)，從而變?yōu)榧訖?quán)網(wǎng)絡(luò)，然后通過(guò)NodeRank算法進(jìn)行關(guān)鍵節(jié)點(diǎn)的挖掘與評(píng)估。用戶自身屬性包括是否通過(guò)V認(rèn)證、粉絲量、好友數(shù)、評(píng)論量和轉(zhuǎn)發(fā)量等特征，在消息傳播過(guò)程中，不同屬性的用戶具有不同的影響力。本文選擇活躍度[8]、關(guān)系強(qiáng)度[9]和權(quán)威系數(shù)作為衡量傳播屬性的指標(biāo)，計(jì)算出用戶系數(shù)作為傳播網(wǎng)絡(luò)節(jié)點(diǎn)的權(quán)值。微博傳播過(guò)程中，由于傳播過(guò)程的某些因素存在差異，比如用戶的偏好[10]、爆炸性內(nèi)容等造成不同類型的微博傳播速度、互動(dòng)程度[11]和轉(zhuǎn)發(fā)層級(jí)不同，從而造成傳播過(guò)程的差異。本文選擇轉(zhuǎn)發(fā)速度、傳播深度和交互指數(shù)作為衡量傳播屬性的指標(biāo)，計(jì)算傳播系數(shù)作為傳播拓?fù)渚W(wǎng)絡(luò)邊上的權(quán)值。

2.1 用戶屬性指標(biāo)

2.1.1 活躍度

微博用戶相同時(shí)間內(nèi)發(fā)布的微博數(shù)越多，說(shuō)明該用戶活躍程度越高，相比其他用戶該用戶的影響力越強(qiáng)，將用戶平均每天發(fā)布的微博數(shù)目定義為用戶的活躍度，用來(lái)衡量用戶的活躍程度，記為A(Activeness)。

(1)

其中，WC(Weibo Counts)為用戶已發(fā)布的微博數(shù),t1為用戶注冊(cè)時(shí)間,t2為微博發(fā)布時(shí)間。

2.1.2 關(guān)系強(qiáng)度

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

(2)

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

2.1.3 權(quán)威系數(shù)

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

(3)

2.2 傳播屬性指標(biāo)

2.2.1 轉(zhuǎn)發(fā)速度

微博的傳播依靠的是與其他用戶產(chǎn)生轉(zhuǎn)發(fā)關(guān)系，當(dāng)產(chǎn)生轉(zhuǎn)發(fā)關(guān)系時(shí)，微博消息才會(huì)傳向下一級(jí)網(wǎng)絡(luò)，才會(huì)對(duì)下一級(jí)用戶產(chǎn)生影響。如果某微博消息傳播速度越大，即單位時(shí)間內(nèi)產(chǎn)生的轉(zhuǎn)發(fā)關(guān)系越多，說(shuō)明其影響力也越大。將單位時(shí)間內(nèi)轉(zhuǎn)發(fā)關(guān)系產(chǎn)生的個(gè)數(shù)定義為轉(zhuǎn)發(fā)速度，記為RV(Report Velocity)。

(4)

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

2.2.2 傳播深度

微博消息被連續(xù)轉(zhuǎn)發(fā)的次數(shù)越多，說(shuō)明該微博的傳播層級(jí)越大，傳播層級(jí)越大說(shuō)明該條微博傳播深度越深，影響程度也越大，這里所講的傳播層級(jí)并不是任意一個(gè)用戶轉(zhuǎn)發(fā)次數(shù)，而是轉(zhuǎn)發(fā)用戶相對(duì)于原微博經(jīng)歷的連續(xù)轉(zhuǎn)發(fā)次數(shù)，將所有轉(zhuǎn)發(fā)用戶中的最大連續(xù)轉(zhuǎn)發(fā)次數(shù)定義為絕對(duì)傳播深度。將某用戶所處的傳播層級(jí)與絕對(duì)傳播深度的比值定義為相對(duì)傳播深度，記為PD(Propagation Depth)。

(5)

其中,Lmax表示傳播過(guò)程中的絕對(duì)傳播深度，Li表示第i個(gè)用戶相對(duì)于原微博所在的轉(zhuǎn)發(fā)層級(jí)。

2.2.3 交互指數(shù)

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

(6)

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

2.3 用戶和傳播影響系數(shù)

在微博節(jié)點(diǎn)的影響力評(píng)估過(guò)程中，對(duì)兩種影響系數(shù)分別選擇三個(gè)屬性，為了確定用戶屬性和傳播屬性的權(quán)值，采用多目標(biāo)決策分析法的思想，將三個(gè)評(píng)價(jià)指標(biāo)合成為一個(gè)權(quán)值，并對(duì)每個(gè)指標(biāo)數(shù)據(jù)進(jìn)行歸一化處理，使得兩個(gè)權(quán)值落在相同的區(qū)間內(nèi)。這種處理方法并不影響數(shù)據(jù)之間的相關(guān)性，能夠保證原始數(shù)據(jù)的真實(shí)情況。通過(guò)分析得知，各個(gè)指標(biāo)之間具有相關(guān)性，并且互相不可替代，適合用加法規(guī)則綜合評(píng)定。為了使得屬性權(quán)值更加準(zhǔn)確，采用層次分析法[12]中構(gòu)建判斷矩陣的方法來(lái)評(píng)估各個(gè)指標(biāo)的權(quán)重。構(gòu)建用戶屬性和傳播屬性的判斷矩陣分別記為A和B。

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

U=0.0702A+0.3707RI+0.5590AI

(7)

其中，U為加權(quán)網(wǎng)絡(luò)拓?fù)鋱D中的節(jié)點(diǎn)權(quán)值；A、RI、AI分別為公式(1)～公式(3)確定的用戶屬性的指標(biāo)數(shù)值。

V=0.6716RV+0.2654PD+0.0629IC

(8)

其中，V為加權(quán)網(wǎng)絡(luò)拓?fù)鋱D中的邊的權(quán)值；RV、PD、IC分別為公式(4)～公式(6)確定的傳播屬性的指標(biāo)數(shù)值。

3 NodeRank算法

3.1 算法思想

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

(9)

其中，P(i)是第i個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，公式如下：

(10)

以上兩式中：ni為節(jié)點(diǎn)i的轉(zhuǎn)發(fā)量，N為總的轉(zhuǎn)發(fā)量，I(i)是第i個(gè)節(jié)點(diǎn)的綜合影響力，I(j)是第j個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的綜合影響力，Ni是第i個(gè)節(jié)點(diǎn)的粉絲數(shù)，Sj是轉(zhuǎn)發(fā)該用戶微博的用戶集合。

由式(7)得，Ui是第i節(jié)點(diǎn)的用戶系數(shù)；由式(8)得，Vij是第i節(jié)點(diǎn)到第j節(jié)點(diǎn)的傳播系數(shù)。

3.2 算法實(shí)現(xiàn)

根據(jù)用戶和傳播屬性評(píng)估模型，得到用戶系數(shù)和傳播系數(shù)，也就得到了拓?fù)鋫鞑ゾW(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)值和邊的權(quán)值。設(shè)加權(quán)傳播網(wǎng)絡(luò)為圖G=(M，N)， 其中，M是所有節(jié)點(diǎn)的集合，即轉(zhuǎn)發(fā)用戶的集合；N是所有邊的集合，即轉(zhuǎn)發(fā)關(guān)系的集合，每一條邊代表一次轉(zhuǎn)發(fā)關(guān)系。根據(jù)加權(quán)之后的網(wǎng)絡(luò)傳播圖，利用微博工具所提供的原始數(shù)據(jù)，將NodeRank算法代入進(jìn)行關(guān)鍵節(jié)點(diǎn)的挖掘和評(píng)估。

Step 1 將采集到的數(shù)據(jù)帶入用戶和傳播屬性評(píng)估模型，得到六個(gè)指標(biāo)的計(jì)算數(shù)值；

Step 2 利用Min-Max 標(biāo)準(zhǔn)化方法對(duì)六個(gè)指標(biāo)的原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，并利用層次分析法中構(gòu)建判斷矩陣的方法計(jì)算各個(gè)指標(biāo)權(quán)重；

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

Step 4 構(gòu)建加權(quán)傳播網(wǎng)絡(luò)圖G=(V，U)，得到轉(zhuǎn)發(fā)關(guān)系；

Step 5 通過(guò)式(10)各個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)關(guān)系計(jì)算第i個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率P(i)；

Step 6 將以上得到的指標(biāo)數(shù)值代入NodeRank算法公式(9)計(jì)算各個(gè)用戶的影響力；

第一，要立足于“我國(guó)是工人階級(jí)領(lǐng)導(dǎo)的，以工農(nóng)聯(lián)盟為基礎(chǔ)的人民民主專政的社會(huì)主義國(guó)家”的國(guó)家性質(zhì)上，堅(jiān)持“人民是國(guó)家的主人”原則，始終站在人民群眾（即思想政治教育的受教育者）的根本立場(chǎng)上，做合乎民族的、符合人民群眾的根本利益的思想政治教育工作。

Step 7 根據(jù)計(jì)算出的各個(gè)用戶的影響力從大到小排序，得到最終影響力排序。

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

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

4.1 數(shù)據(jù)來(lái)源

WeiboEvents[15]是北京大學(xué)可視化與可視分析研究組開(kāi)發(fā)的微博傳播分析工具，通過(guò)直觀的視圖清晰地呈現(xiàn)出一個(gè)事件中微博轉(zhuǎn)發(fā)的過(guò)程，能夠迅速地發(fā)現(xiàn)事件中的關(guān)鍵人物、關(guān)鍵微博、重要觀點(diǎn)，同時(shí)通過(guò)可視化的方式幫助更好地分析微博中事件的發(fā)生與發(fā)展過(guò)程，并可以下載文中各指標(biāo)的原始數(shù)據(jù)。利用WeiboEvents，將原創(chuàng)微博的URL輸入到該工具中，通過(guò)后臺(tái)的采集得到原始數(shù)據(jù)，并通過(guò)可視化分析為下一步的算法分析奠定基礎(chǔ)。

4.2 數(shù)據(jù)預(yù)處理

利用Min-Max 標(biāo)準(zhǔn)化方法對(duì)六個(gè)指標(biāo)的原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，消除不同指標(biāo)數(shù)據(jù)之間因量綱不同帶來(lái)的數(shù)值級(jí)數(shù)上的影響，并且Min-Max標(biāo)準(zhǔn)化方法保留了原始數(shù)據(jù)之間的相關(guān)關(guān)系。Min-Max標(biāo)準(zhǔn)化方法是對(duì)原始數(shù)據(jù)進(jìn)行線性變換。具體算法如下：

設(shè)Xmin和Xmax分別為某種屬性的最小值和最大值，將屬性的一個(gè)原始值X通過(guò)Min-Max標(biāo)準(zhǔn)化映射成在區(qū)間[0，1]的值X′，其公式為：

4.3 計(jì)算結(jié)果及可視化分析

通過(guò)對(duì)原始數(shù)據(jù)的處理和模型的計(jì)算結(jié)果，將結(jié)果代入到本文的影響力評(píng)估算法中，計(jì)算得到七個(gè)影響力較大的關(guān)鍵節(jié)點(diǎn)，這七個(gè)節(jié)點(diǎn)的用戶系數(shù)、傳播系數(shù)、節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率以及最終的影響力和排序結(jié)果如表1所示。

Table 1 Results of the NodeRank algorithm

由表1可得，“21世紀(jì)經(jīng)濟(jì)報(bào)道”具有最大的影響力，這與圖1的可視化結(jié)果相符合，這也不難解釋，因?yàn)樵撚脩羰窃瓌?chuàng)微博，屬于內(nèi)容的生產(chǎn)者，所以影響力最大。由于該微博經(jīng)過(guò)“李開(kāi)復(fù)”的轉(zhuǎn)發(fā)形成二次較大的爆發(fā)，其引起的轉(zhuǎn)發(fā)量比原創(chuàng)微博還要略高，但由于其傳播影響系數(shù)較低，使得綜合影響力并不突出，“薛蠻子”影響力排第三，該結(jié)果與圖1和圖2的可視化結(jié)果完全一致。由圖1和圖2所示，“洪晃ilook”具有第四影響力，但結(jié)果卻排在“李佳佳Audrey”之后，原因是李佳佳節(jié)點(diǎn)是引起微博二次爆發(fā)至關(guān)重要的連接節(jié)點(diǎn)，正是由此節(jié)點(diǎn)之后的轉(zhuǎn)發(fā)才引起了大規(guī)模的二次爆發(fā)，而在“薛蠻子”之后爆發(fā)規(guī)模并不大，所以該節(jié)點(diǎn)應(yīng)比“薛蠻子”更重要，即若沒(méi)有此節(jié)點(diǎn)，就沒(méi)有該微博消息的第二次較大規(guī)模的爆發(fā)。

Figure 1 Hierarchy chart of a broadcast tree圖1 樹(shù)狀轉(zhuǎn)發(fā)層次圖

Figure 2 Topological graph of Weibo spread圖2 微博傳播網(wǎng)絡(luò)拓?fù)鋱D

對(duì)比發(fā)現(xiàn)，“李佳佳Audrey”的用戶影響系數(shù)和傳播影響系數(shù)均為最低，說(shuō)明本文的算法可以挖掘關(guān)鍵節(jié)點(diǎn)。用戶“朱駿”的用戶影響系數(shù)比“21世紀(jì)經(jīng)濟(jì)報(bào)道”要高，但由于其傳播影響系數(shù)與其相差懸殊，導(dǎo)致“朱俊”影響力并不大。用戶“環(huán)保董良杰”的轉(zhuǎn)發(fā)量比用戶“洪晃ilook”要大，但是其用戶影響系數(shù)和傳播影響系數(shù)都比“洪晃ilook”小，導(dǎo)致其綜合影響力偏小。通過(guò)對(duì)各個(gè)用戶的對(duì)比分析表明，本文的算法可以更加準(zhǔn)確、合理、客觀地評(píng)估用戶影響力，其排序結(jié)果與可視化結(jié)果一致，并且可以挖掘關(guān)鍵節(jié)點(diǎn)，計(jì)算結(jié)果可以作為輿情分析等工作的參考。

4.4 不同算法的對(duì)比分析

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

Table 2 Computational results of different algorithms

通過(guò)與基于節(jié)點(diǎn)的度和互信息算法的對(duì)比，我們發(fā)現(xiàn)：兩種對(duì)比算法都將用戶“李佳佳Audrey”排在最后，通過(guò)分析可知，該用戶是連接兩次大規(guī)模爆發(fā)的關(guān)鍵節(jié)點(diǎn)，重要程度明顯不小，說(shuō)明本文算法更加合理。進(jìn)一步與基于互信息的算法對(duì)比，當(dāng)除去用戶“李佳佳Audrey”時(shí)，與本文算法計(jì)算

Table 3 Sorted results of different algorithms

結(jié)果完全一致，說(shuō)明兩種算法在計(jì)算爆發(fā)量比較大的用戶影響力時(shí)，準(zhǔn)確性是相當(dāng)?shù)?，而基于互信息的算法?duì)于爆發(fā)量相對(duì)較小的重要節(jié)點(diǎn)的挖掘不夠準(zhǔn)確。

通過(guò)與傳統(tǒng)的PageRank算法對(duì)比發(fā)現(xiàn)：傳統(tǒng)的PageRank算法認(rèn)為用戶“李佳佳Audrey”是最重要的，說(shuō)明該算法在發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)上具有良好的準(zhǔn)確性，但該結(jié)果有失客觀性，該用戶為關(guān)鍵節(jié)點(diǎn)但并不比爆發(fā)量較大用戶更具影響力。對(duì)比發(fā)現(xiàn)，基于NodeRank算法更勝一籌，基于節(jié)點(diǎn)的度和互信息算法并不可以發(fā)現(xiàn)用戶“李佳佳Audrey”的重要性，將其排在最后，PageRank算法又低估了爆發(fā)節(jié)點(diǎn)的影響力，而NodeRank算法既可以發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)又準(zhǔn)確地評(píng)估了爆發(fā)節(jié)點(diǎn)，說(shuō)明本文的算法更具有客觀性、合理性和準(zhǔn)確性。

5 結(jié)束語(yǔ)

本文基于PageRank算法思想，提出了一種考慮用戶和傳播屬性的節(jié)點(diǎn)影響力評(píng)估算法——NodeRank算法。利用微博分析工具進(jìn)行數(shù)據(jù)采集和可視化分析，將傳播網(wǎng)絡(luò)抽象為雙加權(quán)拓?fù)渚W(wǎng)絡(luò)，根據(jù)WeiboEvents所提供的原始數(shù)據(jù)，將算法代入，對(duì)傳播過(guò)程中的關(guān)鍵節(jié)點(diǎn)進(jìn)行挖掘和評(píng)估。通過(guò)與現(xiàn)有三種經(jīng)典算法的實(shí)驗(yàn)對(duì)比，NodeRank算法具有較好的準(zhǔn)確性，能夠發(fā)現(xiàn)至關(guān)重要的關(guān)鍵節(jié)點(diǎn)和極具影響力的爆發(fā)節(jié)點(diǎn)，并客觀地評(píng)估其重要程度。對(duì)于實(shí)時(shí)的微博事件，計(jì)算的復(fù)雜度還有待提高，降低計(jì)算復(fù)雜度以便快速高效地挖掘關(guān)鍵節(jié)點(diǎn)，將是下一步研究的重點(diǎn)。

[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.

附中文參考文獻(xiàn):

[1] 王小云.基于主題的微博社會(huì)網(wǎng)絡(luò)關(guān)注機(jī)制研究[D]. 武漢:華中科技大學(xué),2013.

[3] 趙英,易平科.基于社交網(wǎng)絡(luò)的蠕蟲(chóng)動(dòng)態(tài)傳播模型[J].計(jì)算機(jī)工程與科學(xué),2013,35(12):34-38.

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

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

[6] 張翼,劉玉華,許凱華,等.一種基于互信息的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[J].計(jì)算機(jī)科學(xué),2013,38(6):88-109.

[7] 李星,鐘志農(nóng),景寧,等.社區(qū)挖掘技術(shù)研究[J].計(jì)算機(jī)工程與科學(xué),2012,34(9):154-159.

[9] 韓忠明,苑麗玲,楊偉杰,等.加權(quán)社會(huì)網(wǎng)絡(luò)中重要節(jié)點(diǎn)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用,2013,33(6):1553-1557.

[12] 劉新憲，朱道立. 選擇與判斷：AHP[M].上海:上?？茖W(xué)普及出版社,1990.

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

尚焱(1990-),男,山東寧津人，碩士生，研究方向?yàn)閃eb 搜索和數(shù)據(jù)挖掘。E-mail:shang.yan@foxmail.com

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

樊欣唯(1992-),女,上海人，碩士生，研究方向?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)路由策略。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會(huì)員(E200010612M)，研究方向?yàn)閿?shù)據(jù)挖掘、粗糙集理論和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，F(xiàn)AN 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61379114)

TP391

A

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

通信地址：100876 北京市海淀區(qū)西土城路10號(hào)北京郵電大學(xué)信息物理融合實(shí)驗(yàn)室教四

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