劉久云,黃廷磊,夏 威,華綠綠

(桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林 541004)

基于多關(guān)系與屬性的主題層次影響力評(píng)估算法

劉久云,黃廷磊,夏 威,華綠綠

(桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林 541004)

為準(zhǔn)確分析和度量微博用戶在主題層次的影響力,提出一種綜合考慮用戶多關(guān)系與個(gè)人屬性的影響力評(píng)估算法。該算法以主題為單位,對(duì)用戶交互行為進(jìn)行分析,構(gòu)建了包含轉(zhuǎn)發(fā)關(guān)系、評(píng)論關(guān)系、復(fù)制關(guān)系和提及關(guān)系的多關(guān)系網(wǎng)絡(luò),并給出轉(zhuǎn)移概率計(jì)算模型;從用戶活躍度、用戶權(quán)威度、博文質(zhì)量、粉絲質(zhì)量4個(gè)角度考慮,構(gòu)建了基于主題的用戶個(gè)人屬性影響力指標(biāo)體系,并使用層次分析法給出各指標(biāo)的權(quán)重;基于PageRank算法思想,提出了融合用戶關(guān)系與屬性特征的影響力計(jì)算方法。通過新浪微博數(shù)據(jù)集的對(duì)比實(shí)驗(yàn),證明了算法的準(zhǔn)確性和有效性。

主題影響力;多關(guān)系網(wǎng)絡(luò);個(gè)人屬性;PageRank;微博

近年來,微博因其即時(shí)性、靈活性、集成性和草根性等特征,成為網(wǎng)絡(luò)輿論的主要來源地和重要集散地。研究發(fā)現(xiàn),微博中存在小部分具有較高影響力的用戶,其發(fā)布的言論觀點(diǎn)往往能影響大批粉絲和輿論走向,對(duì)信息傳播、話題形成、輿論引導(dǎo)起著關(guān)鍵作用[]。

微博輿情的主題極為寬泛,話題涉及政治、經(jīng)濟(jì)、文化等各個(gè)領(lǐng)域。同時(shí),微博用戶覆蓋社會(huì)各個(gè)階層及領(lǐng)域,每個(gè)人在不同主題下的影響力均不相同。用戶有其擅長(zhǎng)的領(lǐng)域,從而能夠成為這個(gè)領(lǐng)域的影響力用戶,在這個(gè)領(lǐng)域內(nèi)能得到更多用戶的認(rèn)可[2]。因此,在大量的微博信息中識(shí)別每個(gè)主題空間下的影響力個(gè)體[3],對(duì)于準(zhǔn)確把握社會(huì)輿情動(dòng)態(tài)進(jìn)而科學(xué)引導(dǎo)輿論導(dǎo)向具有重要的現(xiàn)實(shí)意義。

微博影響力作為微博研究的一個(gè)熱點(diǎn),吸引了眾多學(xué)者的目光,但針對(duì)主題層次的影響力個(gè)體挖掘探討相對(duì)較少。文獻(xiàn)[4]基于改進(jìn)的PageRank提出Topic-sensitive PageRank算法,它優(yōu)于PageRank的地方是其隨機(jī)跳轉(zhuǎn)概率具有主題選擇性,但未考慮用戶之間交互概率的差異性。文獻(xiàn)[5]針對(duì)Twitter數(shù)據(jù)集提出了話題層次的影響力度量方法Twitter Rank,它綜合考慮了話題相識(shí)性和網(wǎng)絡(luò)結(jié)構(gòu),但忽略了提及、評(píng)論和轉(zhuǎn)發(fā)等影響因素。文獻(xiàn)[6]為識(shí)別每個(gè)話題的影響力用戶,考慮了Twitter用戶的發(fā)帖數(shù)、被轉(zhuǎn)發(fā)數(shù)和被提及數(shù)等多個(gè)屬性信息,但未考慮用戶間的多種關(guān)系網(wǎng)絡(luò)。文獻(xiàn)[7]綜合考慮了轉(zhuǎn)發(fā)關(guān)系、回復(fù)關(guān)系、復(fù)制關(guān)系和閱讀關(guān)系4種網(wǎng)絡(luò)關(guān)系,在一定程度上提高了度量準(zhǔn)確度,但未考慮活躍度、博文質(zhì)量等用戶屬性特征。

現(xiàn)有方法均未對(duì)個(gè)體影響力相關(guān)的多關(guān)系網(wǎng)絡(luò)和個(gè)體屬性進(jìn)行有效結(jié)合,不能全面地度量微博用戶在主題級(jí)別的影響力。為此,利用PageRank算法思想,提出一種關(guān)系與屬性的主題層次用戶影響力評(píng)估(comprehensive influence rank,簡(jiǎn)稱CIRank)算法。

1 多關(guān)系網(wǎng)絡(luò)概率計(jì)算模型

微博信息通過關(guān)注網(wǎng)絡(luò)進(jìn)行傳播,用戶發(fā)布的任何信息都出現(xiàn)在其粉絲的主頁(yè)上,粉絲隨時(shí)從其關(guān)注者那里獲取隨機(jī)的新信息。用戶受關(guān)注者的影響,隨機(jī)產(chǎn)生閱讀、收藏、復(fù)制、轉(zhuǎn)發(fā)、評(píng)論和提及等行為。閱讀和收藏行為只是自我吸收的過程,并不會(huì)促進(jìn)消息的對(duì)外傳播,無法對(duì)其他用戶產(chǎn)生影響力。復(fù)制和轉(zhuǎn)發(fā)行為會(huì)使微博內(nèi)容被更多的人分享和傳播,評(píng)論和提及行為則會(huì)吸引更多的人參與話題。后4種行為對(duì)信息傳播范圍和速度產(chǎn)生積極的影響,從而增強(qiáng)用戶的影響力?；谖墨I(xiàn)[7]的多關(guān)系網(wǎng)絡(luò)分析思想,引入促進(jìn)影響力傳播的提及行為,改進(jìn)分析閱讀行為的不足,構(gòu)建主題空間下的包含轉(zhuǎn)發(fā)、評(píng)論、復(fù)制和提及4種網(wǎng)絡(luò)關(guān)系的多關(guān)系網(wǎng)絡(luò),并給出不同網(wǎng)絡(luò)間跳轉(zhuǎn)概率的更合理的計(jì)算方法。

1.1 問題定義

用戶ui受到其關(guān)注者uj的影響,以一定的概率隨機(jī)產(chǎn)生4種明顯的交互行為:1)ui轉(zhuǎn)發(fā)uj的博文; 2)ui評(píng)論uj的博文;3)ui復(fù)制uj的博文;4)ui在其博文中提及uj。據(jù)此,用戶之間的關(guān)注網(wǎng)絡(luò)可分解為轉(zhuǎn)發(fā)、評(píng)論、復(fù)制和提及4種影響關(guān)系網(wǎng)絡(luò)。

將主題t空間下的微博用戶與他們之間的多網(wǎng)絡(luò)關(guān)系抽象為一個(gè)有向加權(quán)圖

其中:k=1,2,3,4分別為轉(zhuǎn)發(fā)、評(píng)論、復(fù)制和提及關(guān)系;Vtk為第k種關(guān)系網(wǎng)絡(luò)中的用戶集合;Etk為相應(yīng)網(wǎng)絡(luò)中的所有關(guān)系邊集;Wtk( Etk)為關(guān)系邊Etk的權(quán)重。

1.2 多關(guān)系網(wǎng)絡(luò)中的轉(zhuǎn)移概率計(jì)算模型

由于用戶擅長(zhǎng)的領(lǐng)域不同,同一主題空間下,不同用戶受到影響后,表現(xiàn)的交互行為習(xí)慣也不同,如部分用戶習(xí)慣轉(zhuǎn)發(fā),部分用戶習(xí)慣評(píng)論,即不同用戶由于受關(guān)注者的影響而停留在4種關(guān)系網(wǎng)絡(luò)的概率不同。同時(shí),用戶在4種影響網(wǎng)絡(luò)內(nèi)部以一定轉(zhuǎn)移概率沿著網(wǎng)絡(luò)隨機(jī)游走。

給定一個(gè)主題t,令用戶vti處于第k種關(guān)系網(wǎng)絡(luò)的概率用Qtk(vti)表示,且有∑Qtk(vti)=1,則主題t k=1空間下的多關(guān)系影響網(wǎng)絡(luò)中用戶間的轉(zhuǎn)移概率矩陣定義為Ptk。

1.2.1 轉(zhuǎn)發(fā)網(wǎng)絡(luò)

定義1 轉(zhuǎn)發(fā)概率矩陣Pt1的每個(gè)元素Pt1(vti, vtj),即用戶vti隨機(jī)轉(zhuǎn)發(fā)vtj微博的概率計(jì)算公式為:

其中:wt1(vti,vt)為主題t空間下轉(zhuǎn)發(fā)網(wǎng)絡(luò)中用戶vtij轉(zhuǎn)發(fā)用戶vtj微博的次數(shù);∑wt1(vti,vt)為主題t vt∈(vt)iout空間下轉(zhuǎn)發(fā)網(wǎng)絡(luò)中用戶vti轉(zhuǎn)發(fā)其所有關(guān)注者的總次數(shù)。

1.2.2 評(píng)論網(wǎng)絡(luò)定義2 評(píng)論概率矩陣Pt2的每個(gè)元素Pt2(vti, vtj),即用戶vti隨機(jī)評(píng)論vtj微博的概率計(jì)算公式為:

其中:wt2(vti,vtj)為主題t空間下評(píng)論網(wǎng)絡(luò)中用戶vti評(píng)論用戶vtj微博的次數(shù);∑wt2(vti,vt)為主題t vt∈(vt)iout空間下評(píng)論網(wǎng)絡(luò)中用戶vti評(píng)論其所有關(guān)注者的總次數(shù)。

1.2.3 復(fù)制網(wǎng)絡(luò)定義3 復(fù)制概率矩陣Pt3的每個(gè)元素Pt3(vti,vtj),即用戶vti隨機(jī)復(fù)制vtj微博的概率計(jì)算公式為:

其中:wt3(vti,vt)為主題t空間下復(fù)制網(wǎng)絡(luò)中用戶vtij與vtj復(fù)制關(guān)系的權(quán)重;∑wt3(vti,vt)為主題t空vt∈(vt)iout間下復(fù)制網(wǎng)絡(luò)中用戶vti與其所有關(guān)注者復(fù)制關(guān)系的權(quán)重。

由于不存在明確的“復(fù)制關(guān)系”,采用文獻(xiàn)[7]的方法進(jìn)行推斷。首先,判斷2篇博文ctm、ctn的時(shí)間間隔Δtrange是否滿足Δtrange=0～1.08×105;若滿足,則判斷博文的相似度S(ctm,ctn)是否高于0.8,相似度計(jì)算使用KL距離(kullback-leibler divergence)方法;若2個(gè)條件均滿足,則認(rèn)為博文ctm復(fù)制了博文ctn。式(3)的wt3(vti,vtj)計(jì)算方法為:

其中:Uti,j為主題t空間下用戶vti與vtj存在復(fù)制關(guān)系的博文二元組集合。f(Δt)為其概率密度函數(shù):

1.2.4 提及網(wǎng)絡(luò)

定義4 提及概率矩陣Pt4的每個(gè)元素Pt4(vti, vtj),即用戶vti在微博中隨機(jī)提及vtj的概率計(jì)算公式為:v∈(v)iout

其中:wt4(vti,vtj)為主題t空間下提及網(wǎng)絡(luò)中用戶vti提及用戶vtj的次數(shù);∑wt4(vti,vt)為主題t空間

vt∈(vt)

iout下提及網(wǎng)絡(luò)中用戶vti提及其所有關(guān)注者的總次數(shù)。

1.3計(jì)算不同網(wǎng)絡(luò)間的跳轉(zhuǎn)概率

由于同一主題空間下不同用戶的交互行為習(xí)慣不同,算法基于實(shí)測(cè)數(shù)據(jù)統(tǒng)計(jì)結(jié)果,計(jì)算用戶在4種關(guān)系網(wǎng)絡(luò)的停留概率。

定義5 主題t空間下用戶vti停留在轉(zhuǎn)發(fā)網(wǎng)絡(luò)的概率定義為:iout

其中:∑wt1(vti,vt)為主題t空間下用戶vti轉(zhuǎn)發(fā)vt∈(vt)iout 4其所有關(guān)注者的總次數(shù);∑∑wtk(vti,vt)為主k=1vt∈(vt)iout題t空間下用戶vti轉(zhuǎn)發(fā)、評(píng)論、復(fù)制和提及所有關(guān)注者的總次數(shù)。定義6 主題t空間下用戶vti停留在評(píng)論網(wǎng)絡(luò)的概率定義為:v∈(v)iout

其中:∑wt2(vti,vt)為主題t空間下用戶vti評(píng)論vt∈(vt)iout其所有關(guān)注者的總次數(shù)。

定義7 主題t空間下用戶vti停留在復(fù)制網(wǎng)絡(luò)的概率定義為:

其中:∑wt2(vti,vt)為主題t空間下用戶vti復(fù)制vt∈(vt)iout其所有關(guān)注者的總次數(shù)。

定義8 主題t空間下用戶vti停留在提及網(wǎng)絡(luò)的概率定義為:

其中:∑wt2(vti,vt)為主題t空間下用戶vti提及vt∈(vt)iout其所有關(guān)注者的總次數(shù)。

2 用戶個(gè)人屬性影響評(píng)估模型

用戶的個(gè)人屬性特征,如活躍度、博文質(zhì)量、名人身份等,也在一定程度上決定其微博影響力大小。由于用戶擅長(zhǎng)的領(lǐng)域不同,其在不同主題空間下的表現(xiàn)也不同,如經(jīng)濟(jì)專家在經(jīng)濟(jì)相關(guān)主題下的博文數(shù)量、原創(chuàng)比和質(zhì)量通常都比較高,相應(yīng)的博文被轉(zhuǎn)發(fā)、評(píng)論次數(shù)也多,則其在主題下對(duì)其他用戶產(chǎn)生的影響力也比較大;相反,其在娛樂、體育等相關(guān)主題下的影響力則要弱很多。因此,算法引入個(gè)人屬性特征對(duì)影響力的作用,構(gòu)建了主題空間下的用戶個(gè)人屬性影響指標(biāo)體系,并使用層次分析法獲得各指標(biāo)的權(quán)重。

2.1 影響指標(biāo)體系構(gòu)建

用戶個(gè)人屬性較多,包括發(fā)布、提及等行為屬性和關(guān)注數(shù)、是否認(rèn)證等狀態(tài)屬性,這是個(gè)人屬性影響因素測(cè)量復(fù)雜的一個(gè)重要原因。由于用戶有一定的擅長(zhǎng)領(lǐng)域,每個(gè)用戶在不同主題空間下的個(gè)體屬性特征也不同。算法以推動(dòng)信息傳播為出發(fā)點(diǎn),以主題為單位,從用戶活躍度、微博質(zhì)量、用戶權(quán)威度和粉絲質(zhì)量4方面考慮,分析大多數(shù)重要的影響指標(biāo)。

1)用戶活躍度?；钴S用戶經(jīng)常發(fā)布新微博或轉(zhuǎn)發(fā)一些高質(zhì)量的博文,從而更能引起關(guān)注;原創(chuàng)微博通常包含了用戶對(duì)新信息獨(dú)到的思想和見解,容易吸引用戶參與討論。所以,用戶越活躍,其對(duì)粉絲產(chǎn)生的影響力可能越大。用戶活躍度考慮平均發(fā)布微博數(shù)、平均轉(zhuǎn)發(fā)微博數(shù)及微博原創(chuàng)比。

主題t空間下,用戶vts平均每天發(fā)布的微博數(shù)為:

其中:d(vts)為用戶vts的微博使用天數(shù);ct1(vts)為用戶vts在主題t空間下發(fā)布的博文總數(shù)。主題t空間下,用戶vts平均每天轉(zhuǎn)發(fā)的微博數(shù)為:

其中:ct2(vts)為用戶vts在主題t空間下轉(zhuǎn)發(fā)的博文總數(shù)。主題t空間下,用戶vts的微博原創(chuàng)比為:

2)微博質(zhì)量。用戶微博被轉(zhuǎn)發(fā)的平均次數(shù)越多,表示博文價(jià)值越大,通過轉(zhuǎn)發(fā)的博文會(huì)以級(jí)聯(lián)的方式繼續(xù)傳播下去,對(duì)更多的用戶產(chǎn)生影響;用戶通常會(huì)評(píng)論認(rèn)同有獨(dú)特視角的微博來表達(dá)自己的見解,平均微博被評(píng)論率越大,表示用戶的博文越容易引起互動(dòng);兩者分別代表了博文影響的廣度和深度。微博質(zhì)量考慮用戶微博被轉(zhuǎn)發(fā)及被評(píng)論的平均次數(shù)。

主題t空間下,用戶vts的微博被轉(zhuǎn)發(fā)的平均次數(shù)為:ct(vt)1s

其中:∑ct4k為用戶vts在主題t空間下的所有博文k=1被轉(zhuǎn)發(fā)的總次數(shù)。主題t空間下,用戶vts的微博被評(píng)論的平均次數(shù)為:ct(vt)1s

其中:∑ct5k為用戶vts在主題t空間下的所有博文k=1被評(píng)論的總次數(shù)。3)用戶權(quán)威度。微博中帶有“V”的VIP實(shí)名認(rèn)證用戶通常為領(lǐng)域?qū)＜摇⒚撕兔浇榫⑷耸?信任度很高,而名人效應(yīng)在信息傳播中的影響力是普通用戶不能比擬的;用戶在主題空間下的被提及率反映了用戶在主題內(nèi)的影響力和被關(guān)注度,用戶被提及率越高,表示在主題內(nèi)的影響力越大。用戶權(quán)威度考慮是否認(rèn)證和被提及率。主題t空間下,用戶vts的被提及率為:

其中:ct6(vts)為用戶vts在主題t空間下的被提及次數(shù),∑ct6(vt)為主題t空間下提及的總?cè)舜螖?shù)。若vt∈Vt用戶vts為認(rèn)證用戶,則認(rèn)證指標(biāo)At7(vts)值為1,否則為0。

4)粉絲質(zhì)量。優(yōu)質(zhì)粉絲越多,則用戶博文的潛在二次傳播范圍越廣,其博文產(chǎn)生的影響力就越大。用戶的粉絲質(zhì)量體現(xiàn)為VIP實(shí)名粉絲比率。

主題t空間下,用戶vts的粉絲認(rèn)證比率為:

其中:NtV,followers(vts)為用戶vts在主題t空間下的多關(guān)系網(wǎng)絡(luò)中的實(shí)名認(rèn)證粉絲數(shù);Ntfollowers(vts)為用戶vts在主題t空間下的多關(guān)系網(wǎng)絡(luò)中的所有粉絲數(shù)。

2.2 基于個(gè)人屬性特征的影響力計(jì)算

定義用戶vts在主題t空間下的個(gè)人屬性特征影響力為:

其中:Atj(vts)為用戶vts在主題t空間下的第j個(gè)影響指標(biāo)值;ωj為第j個(gè)影響指標(biāo)的權(quán)重。

算法采用層次分析法[8]確定不同指標(biāo)在反映用戶個(gè)人屬性特征影響力的權(quán)重。層次分析法可使不同指標(biāo)的差異得到量化,綜合考慮時(shí)更能準(zhǔn)確反映實(shí)際的影響情況。根據(jù)個(gè)人屬性特征影響指標(biāo)體系,將各影響指標(biāo)的權(quán)重表示為ω={ω1,ω2,ω3,ω4,ω5,ω6, ω7,ω8},并將各影響指標(biāo)歸一化,然后用層次分析法確定各指標(biāo)權(quán)重,并驗(yàn)證一致性。

3 融合多關(guān)系與個(gè)人屬性的影響力評(píng)估模型

令主題t空間下用戶vts的綜合影響力為FtCIR(vts),根據(jù)PageRank思想,綜合考慮用戶在4種網(wǎng)絡(luò)中的跳轉(zhuǎn)概率和個(gè)人屬性特征影響因素, FtCIR(vts)的計(jì)算公式為: FtCIR(vts)=d×

其中:k=1,2,3,4分別為主題t空間下的轉(zhuǎn)發(fā)網(wǎng)絡(luò)、評(píng)論網(wǎng)絡(luò)、復(fù)制網(wǎng)絡(luò)和提及網(wǎng)絡(luò);FtPAI( vts)為用戶vts的個(gè)人屬性特征影響力;∑Ft( vt)為主題tPAIj(vt,vt)∈Etijk空間下的第k種影響網(wǎng)絡(luò)中,與用戶vti存在第k種關(guān)系的所有關(guān)注者的個(gè)人屬性特征影響力之和;Nt為主題t空間下的所有用戶數(shù);d為阻尼因子,取經(jīng)驗(yàn)值0.85。

由PageRank算法可知,式(19)是收斂的,經(jīng)過有限次迭代,計(jì)算結(jié)果將趨于穩(wěn)定,從而得出最終的個(gè)體影響力排名。由式(19)可知,用戶在主題空間下的影響力不僅由粉絲的影響力決定,用戶自己在主題空間下的個(gè)人屬性信息也起很大的作用,從而排除了垃圾粉絲的干擾。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)方案

4.1.1 數(shù)據(jù)準(zhǔn)備

從新浪微博平臺(tái)獲取實(shí)驗(yàn)數(shù)據(jù),收集了新浪微博2014年的50個(gè)熱點(diǎn)話題,然后分別選取了社會(huì)、體育、電影、科技和財(cái)經(jīng)領(lǐng)域參與人數(shù)最多的2個(gè)主題,采用分屬于5個(gè)不同領(lǐng)域的10個(gè)主題作為測(cè)試集。選定主題后,獲取主題下參與用戶的所有微博信息和個(gè)人屬性特征信息,包括轉(zhuǎn)發(fā)、評(píng)論等行為屬性和是否認(rèn)證、轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)等狀態(tài)屬性。

數(shù)據(jù)經(jīng)處理后,首先運(yùn)用層次分析法,計(jì)算得到用戶個(gè)人屬性特征影響力的各影響指標(biāo)的權(quán)重,ω= {0.226,0.028,0.011,0.228,0.023,0.228,0.095, 0.161},通過了一致性檢驗(yàn)。

4.1.2 多種影響力分析算法對(duì)比驗(yàn)證

為驗(yàn)證算法CIRank的準(zhǔn)確性和有效性,將CIR-ank與多種相關(guān)算法進(jìn)行對(duì)比驗(yàn)證。主要考慮了以下5種算法:

1)綜合考慮用戶多關(guān)系網(wǎng)絡(luò)與個(gè)人屬性特征的用戶影響力分析算法CIRank。

2)僅考慮多關(guān)系網(wǎng)絡(luò)的影響力挖掘算法Multirelation Rank,計(jì)算公式為:

3)文獻(xiàn)[7]提出的基于多關(guān)系網(wǎng)絡(luò)的微博話題層次的影響力分析算法MultiRank。

4)文獻(xiàn)[5]提出的綜合考慮了話題相識(shí)性和網(wǎng)絡(luò)結(jié)構(gòu)的主題級(jí)別的影響力個(gè)體挖掘算法Twitter Rank。

5)根據(jù)粉絲數(shù)目衡量微博用戶的影響力的Follower Rank算法,Twitter和許多第三方服務(wù)均采用此算法對(duì)影響力進(jìn)行排序。

4.1.3 評(píng)價(jià)指標(biāo)

社交網(wǎng)絡(luò)上的用戶影響力分析的評(píng)測(cè)無統(tǒng)一的衡量標(biāo)準(zhǔn),因此,采用文獻(xiàn)[7]的交叉驗(yàn)證方法得到參考標(biāo)準(zhǔn)結(jié)果值,分別驗(yàn)證每種算法的準(zhǔn)確率、召回率和F值,以此來對(duì)比算法的性能。

交叉驗(yàn)證法為取多種(N種)算法都認(rèn)為正確的結(jié)果作為參考的正確結(jié)果,研究發(fā)現(xiàn)N值為3時(shí),效果最佳。令5種對(duì)比算法得到的前K名高影響力個(gè)體集合,分別表示為U1、U2、U3、U4和U5,則參考標(biāo)準(zhǔn)影響力個(gè)體集合U為5個(gè)結(jié)果集三三相交后取并集的結(jié)果集。

準(zhǔn)確率為預(yù)測(cè)正確的影響力個(gè)體數(shù)與預(yù)測(cè)出的影響力個(gè)體總數(shù)的比值,衡量算法的查準(zhǔn)率;召回率為預(yù)測(cè)正確的影響力個(gè)體數(shù)與參考標(biāo)準(zhǔn)影響力個(gè)體總數(shù)的比值,衡量算法的查全率;F值則為準(zhǔn)確率和召回率的調(diào)和平均值,反映算法的整體性能。

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

4.2.1 算法準(zhǔn)確率、召回率驗(yàn)證

分別采用CIRank算法與4種對(duì)比算法獲得所有主題下的個(gè)體影響力排名,針對(duì)每個(gè)主題,取每種算法排序結(jié)果中的前20、50、100、150、200、300名高影響力個(gè)體,使用交叉驗(yàn)證方法分別計(jì)算算法的6項(xiàng)準(zhǔn)確率、召回率,然后計(jì)算得出各算法在每個(gè)主題下的平均準(zhǔn)確率和召回率,結(jié)果如圖1、2所示。

圖1 各算法在每個(gè)主題下的平均準(zhǔn)確率Fig.1 The average precision rate of each algorithm under each topic

圖2 各算法在每個(gè)主題下的平均召回率Fig.2 The average recall rate of each algorithm under each topic

從圖1、2可看出,在所有主題下,提出的影響力個(gè)體挖掘算法CIRank均可達(dá)到90%以上的準(zhǔn)確率和召回率,在所有算法中表現(xiàn)最佳,證明了該算法的有效性;同時(shí),僅考慮多關(guān)系網(wǎng)絡(luò)的影響力挖掘算法Multi-relation Rank相對(duì)MultiRank算法而言,其準(zhǔn)確率和召回率均有明顯提升,證明算法對(duì)多關(guān)系網(wǎng)絡(luò)概率模型的改進(jìn),即將閱讀網(wǎng)絡(luò)替換為提及網(wǎng)絡(luò)及根據(jù)每個(gè)用戶在各主題下的實(shí)際交互行為習(xí)慣計(jì)算不同網(wǎng)絡(luò)間的停留概率,對(duì)挖掘結(jié)果起到很大改善作用。圖1、2的實(shí)驗(yàn)結(jié)果表明,綜合考慮多關(guān)系網(wǎng)絡(luò)和個(gè)人屬性特征的CIRank算法的平均準(zhǔn)確率和召回率相對(duì)于Multi-relation Rank算法,有非常顯著的提升,說明用戶在每個(gè)主題下的個(gè)人屬性特征起到很大的作用。

4.2.2 算法F值驗(yàn)證

為從整體上驗(yàn)證CIRank算法的性能,綜合考慮準(zhǔn)確率和召回率,分別針對(duì)排序結(jié)果中的前20、50、100、150、200、300名高影響力個(gè)體計(jì)算各算法的F值,然后計(jì)算各算法在每個(gè)主題下的平均F值,實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 各算法在每個(gè)主題下的平均F值Fig.3 The average F value of each algorithm under each topic

從圖3可看出,在所有主題下,CIRank算法相比其他算法整體性能都是最優(yōu)的,Multi-relation Rank算法由于對(duì)多關(guān)系網(wǎng)絡(luò)概率模型的改進(jìn),其整體性能比MultiRank要高一些,Twitter Rank算法和Follower Rank算法的整體性能相對(duì)較差,而Follower-Rank由于僅根據(jù)粉絲數(shù)量進(jìn)行排名,性能最差。

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

以主題為單位,分析了轉(zhuǎn)發(fā)、評(píng)論、復(fù)制和提及4種受影響交互行為,構(gòu)建了用戶多關(guān)系網(wǎng)絡(luò),并給出了基于多關(guān)系網(wǎng)絡(luò)的概率計(jì)算模型。同時(shí),引進(jìn)個(gè)人屬性特征對(duì)影響力的作用,分析了用戶活躍度、微博質(zhì)量、用戶權(quán)威度和粉絲質(zhì)量4個(gè)方面的相關(guān)影響因素,構(gòu)建了主題空間下的個(gè)人屬性特征影響指標(biāo)體系?！敖┦邸焙汀八姟钡牟┪脑瓌?chuàng)性、粉絲質(zhì)量和權(quán)威度等通常都很低,因此,引入個(gè)人屬性影響體系在一定程度上排除了“僵尸粉”和“水軍”對(duì)影響力個(gè)體挖掘結(jié)果的影響。多種對(duì)比算法的交叉驗(yàn)證實(shí)驗(yàn)結(jié)果表明,提出的綜合考慮用戶多關(guān)系網(wǎng)絡(luò)與個(gè)人屬性特征的影響力挖掘算法CIRank優(yōu)于其他相關(guān)算法。構(gòu)建的個(gè)人屬性特征影響指標(biāo)體系采用層次分析法確定各影響指標(biāo)的權(quán)重,一定程度上會(huì)受到人為因素的干擾,研究更準(zhǔn)確的影響指標(biāo)權(quán)重計(jì)算方法將是下一個(gè)研究方向。同時(shí),探究多關(guān)系網(wǎng)絡(luò)和個(gè)人屬性特征影響力的更加有效的結(jié)合方式將是下一步的工作重點(diǎn)。

[1] 肖宇,許煒,商召璽.微博用戶區(qū)域影響力識(shí)別算法及分析[J].計(jì)算機(jī)科學(xué),2012,39(9):38-42.

[2] 尹衍騰,李學(xué)明,蔡孟松.基于用戶關(guān)系與屬性的微博意見領(lǐng)袖挖掘方法[J].計(jì)算機(jī)工程,2013,39(4):184-189.

[3] Rogers E M.Diffusion of Innovations[M].New York: The Free Press,1962:102-120.

[4] Haveliwala T H.Topic-sensitive PageRank[C]//Proceedings of the 11th International Conference on World Wide Web.New York:ACM Press,2002:517-526.

[5] Weng Jianshu,Lim E P,Jiang Jing,et al.Twitterrank: finding topic-sensitive influential twitters[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:261-270.

[6] Pal A,Counts S.Identifying topical authorities in microblogs[C]//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, 2011:45-54.

[7] Ding Zhaoyun,Jia Yan,Zhou Bin,et al.Mining topical influencers based on the multi-relational network in micro-blogging sites[J].China Communications,2013,10 (1):93-104.

[8] 王蓮芬,許樹柏.層次分析法引論[M].北京:中國(guó)人民大學(xué)出版社,1990:42-56.

編輯:梁王歡

Topical influence evaluation algorithm based on multi-relationship and personal attributes

Liu Jiuyun,Huang Tinglei,Xia Wei,Hua Lülü
(School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

To accurately analyze and measure the topical influence of micro-blog users,a new influence evaluation algorithm based on multi-relationship and personal attributes is presented.Taking topic as unit,the multi-relational influence network including repost,comment,copy and mention relations is constructed by analyzing user interaction behavior,and the transition probability calculation model is given.In consideration of user activity,user authority,micro-blog quality and follower quality,an index system of user’s personal attributes influence based on the topic is constructed,and the weight of each indicator is given by using the method of analytic hierarchy process(AHP).Finally,a calculation method of influence based on PageRank is designed by fusing user relations and attributes.A large number of experiments according to real data sets show that the proposed method is accurate and effective.

topical influence;multi-relational network;personal attribute;PageRank;micro-blog

TP393

:A

:1673-808X(2015)04-0329-07

2015-03-26

國(guó)家863計(jì)劃(2012AA011005)

黃廷磊(1971―),男,安徽肥東人,教授,博士,研究方向?yàn)閿?shù)據(jù)挖掘、無線Mesh網(wǎng)絡(luò)等。E-mail:tlhuang@guet.edu.cn

劉久云,黃廷磊,夏威,等.基于多關(guān)系與屬性的主題層次影響力評(píng)估算法[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(4):329-335.