基于PageRank的網(wǎng)絡(luò)社區(qū)意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法

周 飛,高茂庭

(上海海事大學(xué) 信息工程學(xué)院,上海 201306)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展,社交網(wǎng)絡(luò)服務(wù)(Social Network Service,SNS)作為互聯(lián)網(wǎng)應(yīng)用發(fā)展的必備要素,不再局限于信息傳遞,而是與溝通交流、商務(wù)交易類應(yīng)用融合,借助其他應(yīng)用的用戶基礎(chǔ),形成更強(qiáng)大的關(guān)系鏈,從而實(shí)現(xiàn)信息的廣泛、快速傳播。網(wǎng)絡(luò)社區(qū)是具有相同興趣愛(ài)好的網(wǎng)民相互交流、共享資源的虛擬社區(qū),越來(lái)越多的人通過(guò)網(wǎng)絡(luò)社區(qū)分享信息、圖片,表達(dá)意見(jiàn)、觀點(diǎn)或參與話題討論。與線下社區(qū)一樣,網(wǎng)絡(luò)社區(qū)同樣存在社會(huì)分層,不同的是網(wǎng)絡(luò)社區(qū)更多依據(jù)思想和觀點(diǎn)的影響力進(jìn)行劃分,影響力較高的成員就成了群體中的重要角色,即意見(jiàn)領(lǐng)袖。意見(jiàn)領(lǐng)袖通常是網(wǎng)絡(luò)社區(qū)中的活躍分子,是信息的積極傳播者,能夠提供大量信息、意見(jiàn),引起大量關(guān)注并影響社區(qū)中的輿論導(dǎo)向,對(duì)網(wǎng)絡(luò)信息傳播、網(wǎng)絡(luò)營(yíng)銷、廣告投放、輿論引導(dǎo)等方面起著極其重要的作用[1]。因此,對(duì)網(wǎng)絡(luò)社區(qū)中意見(jiàn)領(lǐng)袖的發(fā)現(xiàn)進(jìn)行研究具有重要意義。

“知乎”是社區(qū)氛圍友好與理性、連接各行各業(yè)精英的一個(gè)網(wǎng)絡(luò)問(wèn)答社區(qū)。用戶利用各自的專業(yè)知識(shí)、經(jīng)驗(yàn)和見(jiàn)解,為互聯(lián)網(wǎng)源源不斷地提供高質(zhì)量的信息。知乎不同于微博與傳統(tǒng)社區(qū),社會(huì)身份并非是知乎社區(qū)意見(jiàn)領(lǐng)袖的決定因素,知乎特有的投票機(jī)制和關(guān)注模式催生了大批草根意見(jiàn)領(lǐng)袖[2]。鑒于現(xiàn)有意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法中對(duì)用戶動(dòng)態(tài)行為分析和動(dòng)態(tài)行為所帶來(lái)的真實(shí)瀏覽量考慮不足的問(wèn)題[3-6],本文對(duì)用戶自身影響力、用戶動(dòng)態(tài)行為及其給動(dòng)態(tài)內(nèi)容帶來(lái)的真實(shí)影響等3個(gè)方面進(jìn)行研究,提出一種基于用戶自身影響力、影響力傳播度和PageRank的意見(jiàn)領(lǐng)袖識(shí)別算法。

1 相關(guān)研究

文獻(xiàn)[7]提出的二級(jí)傳播理論是關(guān)于意見(jiàn)領(lǐng)袖的最早研究,該理論指出意見(jiàn)領(lǐng)袖在主要以廣播和報(bào)紙為信息傳播媒介的當(dāng)時(shí)占有不可或缺的地位,媒介信息必須經(jīng)由某些意見(jiàn)領(lǐng)袖才能到達(dá)其他人群。隨著互聯(lián)網(wǎng)的發(fā)展,網(wǎng)絡(luò)社交媒體成為人們?nèi)粘Ｉ畹闹匾ぞ?同時(shí)也吸引了眾多學(xué)者對(duì)其信息傳播、社會(huì)影響力、意見(jiàn)領(lǐng)袖發(fā)現(xiàn)等方面進(jìn)行研究。文獻(xiàn)[8]指出在網(wǎng)絡(luò)社區(qū)中人們通常通過(guò)用戶發(fā)布信息的數(shù)量來(lái)認(rèn)定意見(jiàn)領(lǐng)袖。文獻(xiàn)[9]通過(guò)Twitter網(wǎng)絡(luò)證實(shí)了信息傳播過(guò)程中兩級(jí)傳播理論的存在。文獻(xiàn)[4]用關(guān)注用戶數(shù)量、粉絲數(shù)量、是否被驗(yàn)證身份和發(fā)布的微博數(shù)量等4項(xiàng)數(shù)據(jù)構(gòu)建微博客意見(jiàn)領(lǐng)袖識(shí)別多維模型,對(duì)微博客用戶重要性進(jìn)行評(píng)分。文獻(xiàn)[5]利用從網(wǎng)絡(luò)中采集到的基本數(shù)據(jù),構(gòu)造網(wǎng)絡(luò)話題參與者的“屬性矩陣”,提出意見(jiàn)領(lǐng)袖綜合評(píng)價(jià)算法。文獻(xiàn)[6]選取7個(gè)用戶特征,采用聚類分析方法篩選出具有意見(jiàn)領(lǐng)袖特點(diǎn)的群體。文獻(xiàn)[4-6]都是通過(guò)提取意見(jiàn)領(lǐng)袖屬性特征進(jìn)行歸納分析,提出意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法。但是這些算法都沒(méi)有考慮到用戶與用戶之間的關(guān)注關(guān)系,因此,可能存在用戶大量發(fā)帖但并沒(méi)有人對(duì)其回復(fù)卻被誤認(rèn)為是意見(jiàn)領(lǐng)袖的情況,與客觀事實(shí)存在一定偏差。文獻(xiàn)[10]通過(guò)考慮用戶的興趣空間和回復(fù)關(guān)系,提出基于興趣領(lǐng)域的意見(jiàn)領(lǐng)袖識(shí)別算法。文獻(xiàn)[3,11]將情感傾向性作為用戶之間評(píng)價(jià)的指標(biāo),并作為網(wǎng)絡(luò)權(quán)重分別提出OpinionRank算法和LeaderRank算法。文獻(xiàn)[12]基于話題相似度和用戶間關(guān)注關(guān)系提出TwitterRank算法。文獻(xiàn)[13]發(fā)現(xiàn)消息在微博網(wǎng)絡(luò)中的傳播過(guò)程可近似分解為各個(gè)意見(jiàn)領(lǐng)袖所驅(qū)動(dòng)的子過(guò)程的特性,提出基于消息傳播的微博意見(jiàn)領(lǐng)袖影響力建模方法,并得出影響力衰減指數(shù)的大小以及影響力持續(xù)時(shí)間的長(zhǎng)短與粉絲數(shù)量幾乎無(wú)關(guān)的結(jié)論。文獻(xiàn)[14]綜合考慮用戶自身影響力和用戶之間的鏈接關(guān)系,提出基于用戶影響力的PageRank意見(jiàn)領(lǐng)袖識(shí)別算法,簡(jiǎn)稱UilRank算法。該算法雖然考慮了網(wǎng)絡(luò)論壇中的發(fā)帖數(shù)、回帖數(shù)和被回復(fù)數(shù)、被瀏覽數(shù),但是缺乏用戶動(dòng)態(tài)行為分析,以及存在使動(dòng)態(tài)內(nèi)容閱讀量增長(zhǎng)的來(lái)源指向不明確的現(xiàn)象。

針對(duì)以上算法中用戶動(dòng)態(tài)行為分析缺失和動(dòng)態(tài)內(nèi)容閱讀數(shù)增長(zhǎng)不明確等問(wèn)題,本文以網(wǎng)絡(luò)社區(qū)“知乎”為研究對(duì)象,綜合分析意見(jiàn)領(lǐng)袖影響力因子,在UilRank算法的基礎(chǔ)上,又從用戶動(dòng)態(tài)行為影響傳播度和用戶行為對(duì)動(dòng)態(tài)內(nèi)容帶來(lái)的真實(shí)影響兩個(gè)方面考慮,提出一種基于PageRank的知乎意見(jiàn)領(lǐng)袖影響力發(fā)現(xiàn)算法。其中用戶自身影響力來(lái)源于諸如用戶粉絲數(shù)、獲得贊同數(shù)、回答問(wèn)題數(shù)等用戶自身屬性。用戶動(dòng)態(tài)行為及其對(duì)問(wèn)題的真實(shí)影響將通過(guò)對(duì)用戶動(dòng)態(tài)行為信息和問(wèn)題動(dòng)態(tài)變化信息分析得出,兩者共同決定用戶影響力傳播度的大小,繼而作用于改進(jìn)的PageRank算法中。

2 意見(jiàn)領(lǐng)袖發(fā)現(xiàn)

2.1 算法基礎(chǔ)

PageRank的初衷指的是計(jì)算某個(gè)人在任意次點(diǎn)擊鏈接之后到達(dá)某一網(wǎng)頁(yè)的可能性,在網(wǎng)絡(luò)社區(qū)意見(jiàn)領(lǐng)袖發(fā)現(xiàn)中可把用戶之間的關(guān)注關(guān)系看作是用戶之間的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),通過(guò)分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可獲得用戶影響力排名。因此,用戶影響力可以通過(guò)PageRank算法得出,如式(1)所示。

(1)

其中,PR(u)表示網(wǎng)頁(yè)u的PageRank值,Lu表示指向網(wǎng)頁(yè)u的網(wǎng)頁(yè)集合,N(Ov)表示網(wǎng)頁(yè)v指向其他網(wǎng)頁(yè)的總個(gè)數(shù),d為阻尼因子,表示某頁(yè)面被訪問(wèn)的概率,一般設(shè)為0.85。

文獻(xiàn)[14]在PageRank算法的基礎(chǔ)上,提取用戶屬性特征并給出權(quán)重,將用戶間的回復(fù)次數(shù)作為影響力占比分配原則,提出基于用戶影響力的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法,簡(jiǎn)稱UilRank算法,如式(2)、式(3)所示。

(2)

(3)

其中,R(u)表示用戶u的影響值,Tu為回復(fù)u的用戶集合,Wuv表示用戶u在所有影響用戶v的節(jié)點(diǎn)中所占比例,Iu代表用戶u的初始影響值,kuv表示用戶u和v之間的回復(fù)次數(shù),Bv表示用戶v回復(fù)的用戶集合,通過(guò)數(shù)次迭代直至達(dá)到收斂狀態(tài),得到用戶影響值。

2.2 問(wèn)題及解決思路

在用戶影響力傳播度計(jì)算上,現(xiàn)有意見(jiàn)領(lǐng)袖識(shí)別算法往往采用均分原則平均分配,與實(shí)際網(wǎng)絡(luò)中意見(jiàn)領(lǐng)袖對(duì)不同用戶影響程度不同的這一情形不相符。

意見(jiàn)領(lǐng)袖在對(duì)某一提問(wèn)做出回答行為或者對(duì)某一答案做出點(diǎn)贊行為時(shí),他的行為動(dòng)態(tài)就產(chǎn)生了,繼而將影響他的部分粉絲也對(duì)該提問(wèn)或回答產(chǎn)生行為動(dòng)態(tài)。然而,在這個(gè)過(guò)程中,有部分粉絲看到意見(jiàn)領(lǐng)袖的行為動(dòng)態(tài)后,只是瀏覽了這個(gè)動(dòng)態(tài)內(nèi)容,并沒(méi)有發(fā)出回答或點(diǎn)贊的行為動(dòng)態(tài),因此,不能確定意見(jiàn)領(lǐng)袖是否對(duì)該用戶產(chǎn)生了影響。

為了解決這些問(wèn)題,對(duì)這些屬性值量化處理后得到用戶的初始影響力值,即用戶自身影響力。還將往往被研究者遺忘的動(dòng)態(tài)內(nèi)容被閱讀數(shù)作為一個(gè)考核標(biāo)準(zhǔn),考量用戶在對(duì)某動(dòng)態(tài)內(nèi)容產(chǎn)生行為動(dòng)態(tài)后一段時(shí)間內(nèi)該內(nèi)容閱讀量的真實(shí)變化情況,閱讀量變化情況考量是對(duì)用戶行為動(dòng)態(tài)影響度量存在缺漏現(xiàn)象的補(bǔ)充。然而在實(shí)際網(wǎng)絡(luò)中又存在普通用戶緊隨意見(jiàn)領(lǐng)袖產(chǎn)生行為動(dòng)態(tài)而將意見(jiàn)領(lǐng)袖對(duì)閱讀量變化產(chǎn)生的影響據(jù)為己有的現(xiàn)象,用戶行為動(dòng)態(tài)影響度量又反過(guò)來(lái)制約了此現(xiàn)象,防止普通用戶被認(rèn)為擁有高影響力傳播度。2種度量方法相輔相成,構(gòu)成用戶影響力傳播度。最后將用戶自身影響力和用戶影響力傳播度引入到改進(jìn)的PageRank算法中得到每個(gè)用戶的最終影響力,排名靠前者即為網(wǎng)絡(luò)社區(qū)意見(jiàn)領(lǐng)袖。

3 改進(jìn)的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法

3.1 用戶自身影響力

3.1.1 用戶屬性特征提取

文獻(xiàn)[15-17]指出在Twitter網(wǎng)絡(luò)環(huán)境中,粉絲數(shù)量在信息傳播過(guò)程中和用戶影響力呈弱相關(guān)性。本文通過(guò)獲取到的知乎真實(shí)數(shù)據(jù),對(duì)用戶粉絲數(shù)、獲得贊同數(shù)、回答問(wèn)題數(shù)、獲得感謝數(shù)4個(gè)屬性特征兩兩刻畫相關(guān)性散點(diǎn)圖,如圖1所示,從圖1(a)發(fā)現(xiàn)獲得贊同數(shù)和獲得感謝數(shù)存在一定的線性相關(guān)性,因此,將贊同數(shù)和感謝數(shù)看作是相同的影響因子。另外,從圖1(b)～圖1(d)可以看出用戶粉絲數(shù)、獲得贊同數(shù)和回答問(wèn)題數(shù)這3個(gè)屬性特征不存在線性相關(guān)性,因此,使用這3個(gè)屬性特征對(duì)用戶自身影響力進(jìn)行評(píng)估,其中回答問(wèn)題數(shù)是對(duì)意見(jiàn)領(lǐng)袖活躍度的一種肯定。

圖1 用戶各屬性特征散點(diǎn)圖

3.1.2 用戶屬性特征計(jì)算

從圖1可看出各個(gè)特征數(shù)據(jù)不具備一致性參考標(biāo)準(zhǔn),因此不能直接比較,需要對(duì)每個(gè)特征指標(biāo)進(jìn)行歸一化處理。由于特征數(shù)據(jù)跨度較大,如用戶粉絲數(shù)高的用戶可以達(dá)到百萬(wàn)級(jí)別,低的用戶甚至一個(gè)粉絲都沒(méi)有,因此本文采用對(duì)數(shù)歸一化處理方法。這種處理方式計(jì)算簡(jiǎn)單、運(yùn)算速度快、處理后數(shù)據(jù)跨度小,如式(4)所示。

(4)

其中,Fu表示對(duì)用戶u實(shí)際粉絲數(shù)做歸一化處理后得到的值,fu表示用戶u的實(shí)際粉絲數(shù),fmax代表所有用戶粉絲數(shù)的最大值。同理,對(duì)用戶u獲得贊同數(shù)和回答問(wèn)題數(shù)用式(4)歸一化處理后分別表示為Su、Au。本文定義以下公式計(jì)算用戶u的自身影響力值。

SI(u)=ω1Fu+ω2Su+ω3Au

(5)

其中,SI(u)代表用戶自身影響力值,對(duì)應(yīng)UilRank算法中的Iu,Fu、Su、Au分別是用戶粉絲數(shù)、獲得贊同數(shù)和回答問(wèn)題數(shù)歸一化處理過(guò)后的值,ω1、ω2、ω3代表不同特征的權(quán)重值。為了將各屬性重要程度數(shù)學(xué)化、系統(tǒng)化,本文采用層次分析法確定每個(gè)屬性特征的權(quán)重值,該方法對(duì)于多準(zhǔn)則、多目標(biāo)的系統(tǒng)有較好的判定效果[18]。構(gòu)建以下判斷矩陣:

(6)

通過(guò)計(jì)算,得到各個(gè)屬性特征權(quán)值,一致性檢驗(yàn)結(jié)果為0.079 33<0.1,滿足一致性檢驗(yàn),各屬性特征權(quán)值ωi如表1所示。

表1 屬性特征權(quán)重

3.2 用戶影響力傳播度

在實(shí)際的網(wǎng)絡(luò)傳播中,存在以下2種現(xiàn)象:

1)在意見(jiàn)領(lǐng)袖發(fā)出回答、點(diǎn)贊等行為動(dòng)態(tài)后,部分粉絲接收到意見(jiàn)領(lǐng)袖的動(dòng)態(tài),閱讀了相關(guān)動(dòng)態(tài)內(nèi)容并對(duì)此動(dòng)態(tài)內(nèi)容發(fā)出行為動(dòng)態(tài)。那么意見(jiàn)領(lǐng)袖對(duì)于這部分粉絲的影響是顯而易見(jiàn)并且可以通過(guò)收集動(dòng)態(tài)行為數(shù)據(jù)得到。但是仍然會(huì)存在一些粉絲在閱讀了動(dòng)態(tài)內(nèi)容后,不發(fā)出任何行為動(dòng)態(tài),對(duì)于這部分粉絲則無(wú)法通過(guò)動(dòng)態(tài)行為數(shù)據(jù)知曉意見(jiàn)領(lǐng)袖是否對(duì)其產(chǎn)生了影響。

2)粉絲們會(huì)通過(guò)意見(jiàn)領(lǐng)袖發(fā)出的行為動(dòng)態(tài)瀏覽這一動(dòng)態(tài)內(nèi)容,那么該動(dòng)態(tài)內(nèi)容在該意見(jiàn)領(lǐng)袖發(fā)出回答、點(diǎn)贊等行為之后某個(gè)時(shí)間段內(nèi)的瀏覽數(shù)增長(zhǎng)便可在一定程度上反映該意見(jiàn)領(lǐng)袖的影響力。但是當(dāng)2個(gè)意見(jiàn)領(lǐng)袖A和意見(jiàn)領(lǐng)袖B相近時(shí)間發(fā)出同樣的行為動(dòng)態(tài)時(shí),就無(wú)法確定給動(dòng)態(tài)內(nèi)容帶來(lái)的影響是意見(jiàn)領(lǐng)袖A還是意見(jiàn)領(lǐng)袖B,或者是他們分別帶來(lái)了多少影響。

分析這2種現(xiàn)象可以發(fā)現(xiàn),其實(shí)現(xiàn)象2就是對(duì)現(xiàn)象1中意見(jiàn)領(lǐng)袖影響缺失的一個(gè)補(bǔ)充,現(xiàn)象1則是對(duì)現(xiàn)象2中給動(dòng)態(tài)內(nèi)容帶來(lái)影響重疊的一個(gè)制約。對(duì)于現(xiàn)象1,將采用高行為動(dòng)態(tài)數(shù)據(jù)(即參與者人數(shù)較多的動(dòng)態(tài)內(nèi)容數(shù)據(jù))根據(jù)時(shí)間節(jié)點(diǎn)建立有向無(wú)環(huán)圖計(jì)算用戶行為動(dòng)態(tài)信息下的影響力傳播度。對(duì)于現(xiàn)象2,采用低行為動(dòng)態(tài)數(shù)據(jù)(即參與者人數(shù)較少的動(dòng)態(tài)內(nèi)容數(shù)據(jù))計(jì)算行為動(dòng)態(tài)后的問(wèn)題被瀏覽增長(zhǎng)率,確定基于動(dòng)態(tài)內(nèi)容瀏覽數(shù)增長(zhǎng)下的用戶影響力傳播度。最后將兩者加權(quán)累加得到用戶影響力傳播度。

3.2.1 用戶行為動(dòng)態(tài)信息下的影響力傳播度

在分析以時(shí)間線為基準(zhǔn)的用戶行為動(dòng)態(tài)后發(fā)現(xiàn),該動(dòng)態(tài)行為序列構(gòu)成一個(gè)有向無(wú)環(huán)圖,如圖2所示。

圖2 用戶行為動(dòng)態(tài)結(jié)構(gòu)

圖2描述了影響力傳播的3種情況:

1)在用戶A發(fā)出某一行為動(dòng)態(tài)后,他的粉絲用戶中C、D、E也對(duì)該內(nèi)容發(fā)出行為動(dòng)態(tài),則可認(rèn)為A對(duì)C、D、E產(chǎn)生了影響。

2)用戶H是用戶D、E的共同粉絲,且用戶D、E在用戶H前發(fā)出行為動(dòng)態(tài),那么認(rèn)定用戶H同時(shí)受到用戶D、E的影響。

3)用戶I是用戶B、E的共同粉絲,且用戶E在用戶B之后發(fā)出行為動(dòng)態(tài),用戶I在用戶E之后發(fā)出行為動(dòng)態(tài),那么認(rèn)定用戶I同時(shí)受到用戶B、E的影響,用戶E受到用戶B的影響。

由此,根據(jù)用戶動(dòng)態(tài)行為數(shù)據(jù)建立用戶動(dòng)態(tài)行為結(jié)構(gòu)圖(在圖中認(rèn)定出度為0的節(jié)點(diǎn)為葉子節(jié)點(diǎn)),并依次從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)遍歷,統(tǒng)計(jì)每個(gè)用戶的用戶動(dòng)態(tài)行為影響力值。用戶行為動(dòng)態(tài)信息下的影響力傳播度算法描述如下,其中qid表示動(dòng)態(tài)內(nèi)容編號(hào)。

輸入qid

輸出用戶行為動(dòng)態(tài)影響度Degree

執(zhí)行步驟:

1)Userlist←動(dòng)態(tài)內(nèi)同編號(hào)為qid并以時(shí)間節(jié)點(diǎn)排序的用戶列表;

2)for用戶u∈UserList:{

用戶u的孩子集ChildSetu←UserList中排在u之后的用戶集和用戶u粉絲集的交集;

將添加到ChildrenSetu中每個(gè)用戶c的父集合ParentSetc中;}

3)LeafSet←UserList中孩子集合為空的用戶集合;

4)for用戶u∈LeafSet:{

標(biāo)記v已經(jīng)被查找過(guò);

將v父集合ParentSetv中每個(gè)父節(jié)點(diǎn)p的深度Degreep自加1;

如果p沒(méi)有被查找過(guò)且不在LeafList中,將p添加到LeafSet中;}

5)ifLeafSet不為空,轉(zhuǎn)到4),否則轉(zhuǎn)到6);

6)用對(duì)數(shù)歸一化法對(duì)Degree進(jìn)行歸一化處理;

7)ReturnDegree。

該算法中步驟2)和步驟3)的時(shí)間復(fù)雜度都是O(N),步驟4)、步驟5)為二層循環(huán),時(shí)間復(fù)雜度為O(N2),步驟6)為歸一化處理,時(shí)間復(fù)雜度為O(N)。因此,該算法時(shí)間復(fù)雜度為O(N2)。另外,需要3N的額外空間存儲(chǔ)結(jié)果和中間變量。因此,該算法空間復(fù)雜度為O(N)。

在使用用戶行為動(dòng)態(tài)影響力算法對(duì)每一個(gè)行為動(dòng)態(tài)計(jì)算之后,得到每個(gè)動(dòng)態(tài)下的用戶影響力值,返回歸一化后的用戶動(dòng)態(tài)行為影響力傳播度。

(7)

其中,Degree(qid)[u]為對(duì)第qid號(hào)的動(dòng)態(tài)行為做用戶動(dòng)態(tài)行為影響力算法后用戶u的影響力傳播度,Qlist為用戶行為動(dòng)態(tài)編號(hào)列表。

3.2.2 動(dòng)態(tài)內(nèi)容瀏覽數(shù)增長(zhǎng)下的影響力傳播度

文獻(xiàn)[13]指出在微博網(wǎng)絡(luò)環(huán)境中,在意見(jiàn)領(lǐng)袖發(fā)出一條消息后300 min內(nèi),消息以激增的態(tài)勢(shì)傳播,隨后逐漸減弱,第二天會(huì)有所增長(zhǎng)但影響將逐漸消失。由于微博信息繁雜且動(dòng)態(tài)內(nèi)容更新速度快,表現(xiàn)出快速增長(zhǎng)和快速消亡的特性。但對(duì)于知乎而言,這個(gè)過(guò)程就相對(duì)緩慢一些,因此,以2天為一個(gè)行為動(dòng)態(tài)的影響周期,計(jì)算這段時(shí)間內(nèi)的最快增長(zhǎng),把增長(zhǎng)率作為用戶動(dòng)態(tài)行為給問(wèn)題帶來(lái)實(shí)際影響的考量標(biāo)準(zhǔn)。

本文通過(guò)式(8)～式(10)計(jì)算用戶u給動(dòng)態(tài)內(nèi)容帶來(lái)的平均真實(shí)影響度。

Gn(q,t)=max(B(q,t+1)-B(q,t)),?t∈[t,t+2]

(8)

(9)

(10)

其中,B(q,t)表示問(wèn)題q在t時(shí)刻的被瀏覽次數(shù),Gn(q,t)表示問(wèn)題q在[t,t+2]時(shí)間區(qū)間內(nèi)被瀏覽次數(shù)增長(zhǎng)最大值,utime表示用戶u對(duì)問(wèn)題q產(chǎn)生行為動(dòng)態(tài)的時(shí)刻,max(Gn(q,T))表示在整個(gè)數(shù)據(jù)集時(shí)間段中問(wèn)題q的被瀏覽次數(shù)增長(zhǎng)最大值,Gr(q,u)表示用戶u在問(wèn)題q下的影響力比率,Qir(u)表示用戶u在眾多問(wèn)題動(dòng)態(tài)中給問(wèn)題帶來(lái)的平均真實(shí)影響度。

綜合用戶行為動(dòng)態(tài)信息下的影響力傳播度和行為動(dòng)態(tài)給動(dòng)態(tài)內(nèi)容帶來(lái)的實(shí)際影響度得到用戶影響力傳播度 (User Influence Transfer Degree,UITD)。

(11)

3.3 ZhihuRank意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法

本文在PageRank算法的思想基礎(chǔ)上提出了基于用戶自身影響力、用戶影響力傳播度和PageRank的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法,簡(jiǎn)稱ZhihuRank算法,如式(12)、式(13)所示。

(12)

(13)

其中,ZR(u)表示用戶的影響力值。d為阻尼因子,表示用戶受到影響的概率,通常在(0,1)之間,本文設(shè)為0.85。FRu表示用戶u的粉絲集合,對(duì)應(yīng)于UilRank算法中的Tu集合。W(u,v)表示用戶u在用戶v關(guān)注的人集合中影響力傳播度的占比。FEv表示用戶v關(guān)注的人的集合,對(duì)應(yīng)于UilRank算法中的Bv集合。SI(u)表示用戶自身初始影響力值。UITD(u)代表用戶u的影響力傳播度。

假設(shè)網(wǎng)絡(luò)社區(qū)個(gè)體數(shù)為N,設(shè)定2個(gè)結(jié)束標(biāo)志,一個(gè)為網(wǎng)絡(luò)循環(huán)迭代次數(shù)iterations,另一個(gè)為α,表示每個(gè)個(gè)體當(dāng)前ZR值和上一次迭代結(jié)果ZRold值的差值的閾值。算法結(jié)束后ZR為最終用戶影響力值,SORT()是以ZR為基準(zhǔn)的逆排序函數(shù)。ZhihuRank算法描述如下:

輸入N,iteration,a

輸出用戶影響力排名

執(zhí)行步驟:

1)對(duì)ZR進(jìn)行初始化,將所有節(jié)點(diǎn)ZR值設(shè)為1。

2)使用式(12)、式(13)計(jì)算每個(gè)節(jié)點(diǎn)的ZR值。

3)如果iteration≤0或者對(duì)于任意用戶u都有|ZR(u)-ZRold(u)|

4)iteration←iteration-1,轉(zhuǎn)到步驟2)。

5)ReturnSORT(ZR)。

該算法中步驟1)為初始化賦值,時(shí)間復(fù)雜度為O(N)。步驟2)～步驟4)有3層循環(huán),時(shí)間復(fù)雜度為iteration×O(N2),但是在實(shí)際操作中,可以對(duì)式(13)中的W(u,v)進(jìn)行預(yù)處理,利用額外空間換取時(shí)間,將時(shí)間復(fù)雜度降低為iteration×2×O(N)。iteration為常數(shù),因此,該算法的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(N)。

4 實(shí)驗(yàn)設(shè)置與結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)收集與軟硬件環(huán)境

本文以知乎問(wèn)答社區(qū)為數(shù)據(jù)來(lái)源,通過(guò)爬蟲以作者的知乎賬號(hào)為種子,收集作者關(guān)注的人的信息并存入到數(shù)據(jù)庫(kù)中,再迭代循環(huán)爬取數(shù)據(jù)庫(kù)中沒(méi)有被爬取過(guò)的用戶,用戶信息數(shù)據(jù)包含用戶ID、用戶名、粉絲數(shù)、關(guān)注數(shù)、獲得贊同數(shù)、獲得感謝數(shù)、回答問(wèn)題數(shù)等。

在分析了用戶屬性特征散點(diǎn)圖后,為了方便爬取用戶動(dòng)態(tài)行為信息,將可能是意見(jiàn)領(lǐng)袖的用戶抽取出建立小型爬取源,減少不必要的網(wǎng)絡(luò)流量。隨后抓取此爬取源中用戶行為動(dòng)態(tài)信息和動(dòng)態(tài)內(nèi)容變化數(shù)據(jù),分別存入數(shù)據(jù)庫(kù)中。用戶行為動(dòng)態(tài)數(shù)據(jù)包含用戶ID、問(wèn)題唯一標(biāo)識(shí)qid、動(dòng)態(tài)產(chǎn)生時(shí)間、動(dòng)態(tài)類型等。動(dòng)態(tài)內(nèi)容變化數(shù)據(jù)包含問(wèn)題唯一標(biāo)識(shí)qid、問(wèn)題標(biāo)題、爬取時(shí)間、當(dāng)前閱讀量等。本文共收集了約14萬(wàn)知乎用戶信息、近8.5萬(wàn)條用戶行為動(dòng)態(tài)信息、將近22萬(wàn)條問(wèn)題變化信息及用戶間的關(guān)注關(guān)系信息作為實(shí)驗(yàn)數(shù)據(jù)集。

實(shí)驗(yàn)軟件環(huán)境為Python,版本2.7.10;數(shù)據(jù)庫(kù)使用非關(guān)系型數(shù)據(jù)庫(kù)MongoDB,版本3.2.9;硬件環(huán)境為macOS,內(nèi)存8 GB,處理器1.6 GHz Intel Core i5。

4.2 算法評(píng)測(cè)標(biāo)準(zhǔn)

目前對(duì)于影響力模型評(píng)測(cè)還沒(méi)有一個(gè)統(tǒng)一的評(píng)測(cè)標(biāo)準(zhǔn),大多研究者采用覆蓋度[19]和核心率[20]作為評(píng)價(jià)指標(biāo),或使用人工評(píng)價(jià)的方法。

覆蓋度是從用戶間網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度考慮,通過(guò)意見(jiàn)領(lǐng)袖發(fā)出的行為動(dòng)態(tài),在直接或者間接影響的用戶數(shù)占全部用戶數(shù)的比重來(lái)衡量意見(jiàn)領(lǐng)袖的影響力。覆蓋度分為單步覆蓋度和全路徑覆蓋度。本文采用單步覆蓋度和帶阻尼因子的全路徑覆蓋度對(duì)算法進(jìn)行定性評(píng)測(cè)。

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

4.3.1 意見(jiàn)領(lǐng)袖影響力排名

為了驗(yàn)證算法的合理性,將本文提出的ZhihuRank意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法與PageRank算法、UilRank算法進(jìn)行對(duì)比實(shí)驗(yàn),3種算法Top-10排名的結(jié)果如表2所示。從表2可以看出,3種算法排名在意見(jiàn)領(lǐng)袖用戶選取方面還是比較接近的,由于篇幅所限,不能顯示更多的意見(jiàn)領(lǐng)袖用戶。在使用UilRank算法計(jì)算用戶初始影響力時(shí)數(shù)據(jù)集有稍許差別,通過(guò)分析,把本文中的用戶獲得贊同數(shù)當(dāng)作UilRank的被回復(fù)數(shù),用于計(jì)算用戶的初始影響力。

表2 3種算法結(jié)果對(duì)比

從表2還可以發(fā)現(xiàn),位于ZhihuRank排名前10位的用戶大多可以在PageRank或UilRank排名中找到,不同的是他們的排序位置存在一定的差異。圖3為表2中所有用戶的屬性特性值在這些用戶總特征值的加權(quán)占比情況。

圖3 用戶加權(quán)屬性值占比堆積柱狀圖

用戶“zhang-jia-wei”在PageRank和ZhihuRank算法排名中都處于第一位,這得益于他的高粉絲和高獲贊以及有著較高的影響力傳播度,且該用戶是知乎網(wǎng)絡(luò)上公認(rèn)的意見(jiàn)領(lǐng)袖級(jí)用戶。用戶“excited-vczh”在UilRank算法排名中居于第4位但是在ZhihuRank中卻未進(jìn)前10(第11位),而且他的屬性占比情況也不差,原因在于UilRank算法中回帖數(shù)擁有較大屬性特征權(quán)重,在本數(shù)據(jù)集中表現(xiàn)為回答問(wèn)題數(shù)。但是在本文算法中,弱化了回答問(wèn)題數(shù)這個(gè)屬性,認(rèn)為粉絲數(shù)和獲得贊同數(shù)更為重要,相比于回答問(wèn)題數(shù)更能體現(xiàn)用戶的影響力,因此在ZhihuRank算法排名前10位中沒(méi)有用戶“excited-vczh”。

從圖3中還發(fā)現(xiàn)ZhihuRank算法排名結(jié)果中的第2位、第3位用戶“gejinyuban”和用戶“ma-bo-yong”在特征數(shù)據(jù)占比中表現(xiàn)平平,原因有二。其一,從表3中可知他們有著高影響力傳播度,而且雖然在數(shù)據(jù)占比上沒(méi)有突出表現(xiàn),但是基數(shù)很大,計(jì)算出的自身影響力實(shí)際并不低。其二,很多高質(zhì)量用戶(包括Top-10中的用戶)是他們的粉絲,表3中給出了擁有Top-30的粉絲數(shù),由于Top-30用戶關(guān)注關(guān)系過(guò)于復(fù)雜,圖4給出Top-10用戶間的關(guān)注關(guān)系,從圖中可以看出這2位用戶的入度都非常高,說(shuō)明了他們位于前列的合理性。

表3 用戶影響力信息和Top-30粉絲擁有量

圖4 Top-10用戶間關(guān)注關(guān)系

綜合以上實(shí)驗(yàn)結(jié)果和分析,ZhihuRank算法考慮了用戶的自身屬性特征和用戶動(dòng)態(tài)行為影響力傳播度,能夠更準(zhǔn)確、有效地識(shí)別網(wǎng)絡(luò)社區(qū)中的意見(jiàn)領(lǐng)袖,且結(jié)果更具合理性。

4.3.2 算法評(píng)測(cè)結(jié)果

為了定性評(píng)估本文算法的有效性,分別使用單步覆蓋度評(píng)價(jià)方法和傳播影響力覆蓋度評(píng)價(jià)算法對(duì)Top-k意見(jiàn)領(lǐng)袖的影響力覆蓋度進(jìn)行測(cè)評(píng),實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

圖5 單步覆蓋度評(píng)測(cè)結(jié)果

圖6 傳播覆蓋度評(píng)測(cè)結(jié)果

從圖5、圖6可知,ZhihuRank算法比其他2個(gè)算法不管在單步覆蓋還是傳播覆蓋上都具有較大的影響力覆蓋度,且有較明顯優(yōu)勢(shì),可見(jiàn)算法的有效性。從圖5中還可發(fā)現(xiàn)在單步覆蓋度評(píng)價(jià)中UilRank算法起初比PageRank的算法覆蓋度還要低,說(shuō)明在單步影響力傳播環(huán)境下的UilRank算法并不能發(fā)揮其效果。PageRank算法是完全基于拓?fù)洵h(huán)境下循環(huán)迭代傳播的,所以在一定程度上比基于用戶屬性得到的影響力覆蓋度更有優(yōu)勢(shì)。此外,還發(fā)現(xiàn)前50名意見(jiàn)領(lǐng)袖的影響力可以覆蓋大約90%的用戶。

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

在線網(wǎng)絡(luò)社區(qū)的興起給意見(jiàn)領(lǐng)袖發(fā)現(xiàn)研究提供了理想的實(shí)驗(yàn)平臺(tái)。同時(shí),這方面的研究也反過(guò)來(lái)影響著網(wǎng)絡(luò)社區(qū)和人們的真實(shí)生活。

本文通過(guò)收集的知乎網(wǎng)絡(luò)社區(qū)數(shù)據(jù),對(duì)用戶的影響力進(jìn)行分析,從用戶自身影響力、用戶動(dòng)態(tài)行為及其給動(dòng)態(tài)內(nèi)容帶來(lái)的真實(shí)影響這3個(gè)方面進(jìn)行研究,根據(jù)用戶自身屬性特征值計(jì)算出用戶自身影響力,再通過(guò)用戶動(dòng)態(tài)行為及其對(duì)動(dòng)態(tài)內(nèi)容產(chǎn)生的影響計(jì)算出用戶影響力的傳播力度,最后利用改進(jìn)后的ZhihuRank算法計(jì)算用戶的最終影響力,發(fā)現(xiàn)知乎網(wǎng)絡(luò)中的意見(jiàn)領(lǐng)袖。雖然本文的研究對(duì)象是知乎網(wǎng)絡(luò),但是提出的算法同樣適用于諸如微博、論壇等類似網(wǎng)絡(luò)社區(qū)。

但是,本文算法還有不足之處,比如在獲取用戶動(dòng)態(tài)行為信息時(shí)可以更細(xì)致地將用戶行為進(jìn)行區(qū)分。在接下來(lái)的工作中,將進(jìn)一步改進(jìn)算法,收集更細(xì)致的用戶動(dòng)態(tài)行為和問(wèn)題動(dòng)態(tài)變化信息。此外,將對(duì)問(wèn)題文本內(nèi)容、內(nèi)容主題、個(gè)人情感這些因素加入到影響力分析上,使研究更加精準(zhǔn)、全面。

[1] FREEMANL C.Centrality in Social Networks Conceptual Clarification[J].Social Networks,1979,1(3):215-239.

[2] 王秀麗.網(wǎng)絡(luò)社區(qū)意見(jiàn)領(lǐng)袖影響機(jī)制研究——以社會(huì)化問(wèn)答社區(qū)“知乎”為例[J].國(guó)際新聞界,2014,36(9):47-57.

[3] YU Xiao,LIN Xia.Understanding Opinion Leaders in Bulletin Board Systems:Structures and Algorithms[C]// Proceedings of the 35th Conference on Local Computer Networks.Washington D.C.,USA:IEEE Press,2010:1062-1067.

[4] 王君澤,王雅蕾,禹 航,等.微博客意見(jiàn)領(lǐng)袖識(shí)別模型研究[J].新聞與傳播研究,2011(6):81-88.

[5] 丁雪峰,胡 勇,趙 文,等.網(wǎng)絡(luò)輿論意見(jiàn)領(lǐng)袖特征研究[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2010,42(2):145-149.

[6] 王 玨,曾劍平,周葆華,等.基于聚類分析的網(wǎng)絡(luò)論壇意見(jiàn)領(lǐng)袖發(fā)現(xiàn)方法[J].計(jì)算機(jī)工程,2011,37(5):44-46.

[7] LAZARSFELD P F,BERELSON B,GAUDET H.The People’s Choice:How the Voter Makes Up His Mind in a Presidential Campaign[M].New York,USA:[s.n.],2007:229-233.

[8] YOO Y,ALAVI M.Emergent Leadership in Virtual Teams:What Do Emergent Leaders Do?[J].Infor-mation & Organization,2004,14(1):27-58.

[9] WU Shaomei,HOFMAN J M,MASON W A,et al.Who Says What to Whom on Twitter[C]//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2011:705-714.

[10] ZHAI Zhongwu,XU Hua,JIA Peifa.Identifying Opinion Leaders in BBS[C]//Proceedings of International Conference on Intelligent Agent Technology.Sydney,Australia:[s.n.],2008:398-401.

[11] ZHOU Hengmin,ZENG D.Finding Leaders from Opinion Networks[C]//Proceedings of IEEE International Conference on Intelligence and Security Informatics.Washington D.C.,USA:IEEE Press,2009:266-268.

[12] WENG Jianshu,LIM E P,JIANG Jing,et al.TwitterRank:Finding Topic-sensitive Influential Twitterers[C]//Proceedings of ACM International Conference on Web Search & Data Mining.New York,USA:ACM Press,2010:261-270.

[13] 王晨旭,管曉宏,秦 濤,等.微博消息傳播中意見(jiàn)領(lǐng)袖影響力建模研究[J].軟件學(xué)報(bào),2015,26(6):1473-1485.

[14] 吳 渝,馬璐璐,林 茂,等.基于用戶影響力的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(3):561-565.

[15] ASUR S,HUBERMAN B A,SZABO G,et al.Trends in Social Media:Persistence and Decay[EB/OL].(2011-02-05).http://www.hpl.hp.com/research/scl/papers/trends/trends_web.pdf.

[16] CHA M,HADDADI H,BENEVENUTOF,et al.Measuring User Influence in Twitter:The Million Follower Fallacy[C]//Proceedings of the 4th International Conference on Weblogs and Social Media.Washington D.C.,USA:[s.n.],2010.

[17] KWAK H,LEE C,PARK H,et al.What is Twitter,A Social Network or A News Media?[C]//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2010:591-600.

[18] 許樹柏.層次分析法原理[M].天津:天津大學(xué)出版社,1988.

[19] SONG Xiaodan,CHI Yun,HINO K,et al.Identifying Opinion Leaders in the Blogosphere[C]//Proceedings of the 16th ACM Conference on Information and Knowledge Management.New York,USA:ACM Press,2007:971-974.

[20] MIAO Qingliang,ZHANG Shu,MENG Yao,et al.Domain-sensitive Opinion Leader Mining from Online Review Communities[C]//Proceedings of the 22nd International Conference on World Wide Web Companion.New York,USA:ACM Press,2013:187-188.