一種社交網(wǎng)絡(luò)用戶領(lǐng)導(dǎo)者挖掘算法

宋倩倩, 張 波, 胡斯卉, 徐 倩, 彭如香

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234;2.公安部第三研究所,上海 201204)

?

一種社交網(wǎng)絡(luò)用戶領(lǐng)導(dǎo)者挖掘算法

宋倩倩1, 張 波1, 胡斯卉1, 徐 倩1, 彭如香2

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234;2.公安部第三研究所,上海 201204)

社交網(wǎng)絡(luò)中的用戶領(lǐng)導(dǎo)者挖掘是用戶影響力分析的重要問題.提出一種基于用戶影響力評估的社交網(wǎng)絡(luò)用戶領(lǐng)導(dǎo)者挖掘算法.首先,描述問題模型以及模型相關(guān)定義;其次,提出了基于用戶影響力和用戶活躍度計(jì)算的用戶領(lǐng)導(dǎo)力評估方法;最后,依據(jù)用戶領(lǐng)導(dǎo)力和用戶中心度計(jì)算實(shí)現(xiàn)用戶領(lǐng)導(dǎo)者的挖掘.實(shí)驗(yàn)印證了該方法對于社交網(wǎng)絡(luò)挖掘用戶領(lǐng)導(dǎo)者的可行性和有效性.

社交網(wǎng)絡(luò); 用戶領(lǐng)導(dǎo)者挖掘; 用戶影響力; 活躍度; 中心性

0 引 言

隨著Facebook、Twitter等社交類網(wǎng)站的迅速發(fā)展[1],越來越多的研究開始關(guān)注信息傳播[2]和用戶作用分析[3],以實(shí)現(xiàn)社交網(wǎng)絡(luò)用戶影響力的有效評估,而在用戶影響力評估的研究中,用戶領(lǐng)導(dǎo)者挖掘是一個(gè)重要的課題.用戶領(lǐng)導(dǎo)者即用戶群體中領(lǐng)導(dǎo)力強(qiáng)的用戶,用戶領(lǐng)導(dǎo)者挖掘分析有益于增強(qiáng)社交網(wǎng)絡(luò)信息的傳播分析及控制等方面工作.

目前很多研究表明,用戶影響力的研究是實(shí)現(xiàn)挖掘用戶領(lǐng)導(dǎo)者的關(guān)鍵.Page等[4]基于用戶間關(guān)系對用戶進(jìn)行PageRank排序?qū)崿F(xiàn)分析用戶影響力;呂琳媛等[5]基于PageRank算法的改進(jìn),提出了LeaderRank算法,通過添加公共節(jié)點(diǎn)實(shí)現(xiàn)連接網(wǎng)絡(luò)中的全部節(jié)點(diǎn),計(jì)算出用戶的影響力;周文安等[6]基于用戶的好友數(shù)量及質(zhì)量提出了UserRank模型,分析用戶影響力;Cha等[7]基于用戶度數(shù),用戶在內(nèi)容中被提及的次數(shù),用戶內(nèi)容被轉(zhuǎn)發(fā)或引用次數(shù)等指標(biāo)分析用戶影響力.然而,上述研究均未考慮用戶對關(guān)注其用戶的影響力不同的問題,未考慮到用戶在單位時(shí)間內(nèi)的活躍度問題,忽視了這些因素對于用戶領(lǐng)導(dǎo)者挖掘的影響.

本文作者針對以往研究中存在的不足,提出了一種基于用戶影響力評估的社交網(wǎng)絡(luò)用戶領(lǐng)導(dǎo)者挖掘方法.首先,描述問題模型以及模型相關(guān)定義;其次,提出了基于用戶影響力和用戶活躍度計(jì)算的用戶領(lǐng)導(dǎo)力評估方法;最后,依據(jù)用戶領(lǐng)導(dǎo)力和用戶中心度計(jì)算實(shí)現(xiàn)用戶領(lǐng)導(dǎo)者的挖掘.

第1節(jié)介紹了之前人們所做的一些相關(guān)工作與研究;第2節(jié)提出了社交網(wǎng)絡(luò)用戶領(lǐng)導(dǎo)者的挖掘算法;第3節(jié)介紹了在不同的數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)并且對實(shí)驗(yàn)結(jié)果進(jìn)行了分析;第4節(jié)介紹了所做的主要工作以及在未來研究的重點(diǎn).

1 相關(guān)工作

近年來,對用戶影響力進(jìn)行研究的方法很多,比較典型的有以下幾種.

楊長春等[8]基于傳統(tǒng)的PageRank算法的改進(jìn),提出了一種新的中文微博社區(qū)博主影響力的評估算法,通過研究微博中的微博博主的交互行為,構(gòu)建微博社區(qū)網(wǎng)絡(luò)模型,并且對網(wǎng)絡(luò)特征進(jìn)行統(tǒng)計(jì)和分析,基于PageRank算法,建立了新的評價(jià)指標(biāo),從而評估微博博主在微博社區(qū)中的影響力.

肖宇等[9]以人人網(wǎng)為例,對社交網(wǎng)絡(luò)進(jìn)行分析,提出了社交網(wǎng)絡(luò)中用戶區(qū)域影響力評估算法,該算法的主要思想是:用戶在區(qū)域中的影響力與用戶傳播信息的意愿和社會(huì)傳播能力有關(guān),定量地對每個(gè)用戶的傳播影響力進(jìn)行度量,從而得出用戶在區(qū)域中的影響力.

馬俊等[10]首先根據(jù)微博轉(zhuǎn)發(fā)關(guān)系構(gòu)建信息傳播網(wǎng),然后在該網(wǎng)絡(luò)中從傳播速度、范圍和距離3個(gè)方面對信息傳播特征進(jìn)行定量分析.在此基礎(chǔ)上,利用個(gè)人屬性的統(tǒng)計(jì)數(shù)據(jù)對各傳播特征進(jìn)行回歸分析,找出最能反映用戶影響力的屬性特征,進(jìn)而利用其對用戶影響力進(jìn)行預(yù)測.

黎明等[11]提出一種基于行為權(quán)值的微博用戶影響力度量算法.首先對網(wǎng)絡(luò)用戶的轉(zhuǎn)發(fā)、評論和提及等用戶行為進(jìn)行分析,然后采用最小二乘支持向量機(jī)合理確定他人權(quán)值,建立傳播影響力度量模型.

以上研究主要依賴于對用戶影響力的研究大多數(shù)都是從用戶的粉絲數(shù)、轉(zhuǎn)發(fā)、評論、提及用戶發(fā)布信息的用戶數(shù)等方面對用戶的影響力進(jìn)行評估,尚未充分考慮用戶對關(guān)注他的用戶的影響力不同,以及用戶在一段時(shí)間內(nèi)的活躍度等重要因素.本文作者主要針對用戶對關(guān)注他的用戶影響力開展研究.

2 用戶領(lǐng)導(dǎo)者挖掘算法模型

首先給出用戶領(lǐng)導(dǎo)者挖掘算法模型(MULM)及其相關(guān)定義.

2.1 問題建模

通過引入圖論方法對社交網(wǎng)絡(luò)和用戶領(lǐng)導(dǎo)者挖掘算法模型進(jìn)行建模,如下所示:

2) 用戶領(lǐng)導(dǎo)者挖掘算法模型:從社交網(wǎng)絡(luò)用戶集合中選取用戶領(lǐng)導(dǎo)力及用戶中心性強(qiáng)的前k個(gè)用戶加入用戶領(lǐng)導(dǎo)者集合(CUL),選取到的用戶領(lǐng)導(dǎo)者可以表示為:u∈V并且u∈CUL.用戶領(lǐng)導(dǎo)者和社交網(wǎng)絡(luò)的關(guān)系可以表示為:CUL?V.

2.2 相關(guān)定義

為了便于MULM中的相關(guān)計(jì)算,有以下定義:

定義1 粉絲(Fans).粉絲是指社交網(wǎng)絡(luò)中關(guān)注其他用戶的用戶,將關(guān)注者定義為該用戶的粉絲.

定義2 用戶影響力(UI).用戶影響力是指用戶對社交網(wǎng)絡(luò)中其他用戶的影響力,由粉絲對他的關(guān)注程度、粉絲的影響力及粉絲距離他的遠(yuǎn)近程度的規(guī)模等決定,并且UI∈[0,1].

針對新加入用戶,將用戶初始影響力設(shè)為0.01.

定義3 關(guān)注程度(AD).關(guān)注程度是指用戶之間關(guān)注關(guān)系的數(shù)值化度量,AD∈[0,1].

定義4 用戶領(lǐng)導(dǎo)力(ULD).用戶領(lǐng)導(dǎo)力是指在社交網(wǎng)絡(luò)中的用戶對其他用戶的領(lǐng)導(dǎo)能力,由用戶影響力和粉絲對其的關(guān)注程度組成.

定義5 用戶中心性(UC).用戶中心性是指用戶在社交網(wǎng)絡(luò)中的位置,即經(jīng)過他的用戶數(shù)越多,則說明用戶的中心性越明顯,UC∈[0,1].

定義6 用戶領(lǐng)導(dǎo)者(UL).用戶領(lǐng)導(dǎo)者就是在社交網(wǎng)絡(luò)中用戶領(lǐng)導(dǎo)力強(qiáng)并且中心性強(qiáng)的用戶,而用戶領(lǐng)導(dǎo)者的選取是根據(jù)社交網(wǎng)絡(luò)的需要選取的,不同的社交網(wǎng)絡(luò)選取用戶領(lǐng)導(dǎo)者的數(shù)目不同.可依據(jù)取值不同選取k個(gè)用戶領(lǐng)導(dǎo)者.

用戶領(lǐng)導(dǎo)者挖掘的原理如圖1所示.

圖1 用戶領(lǐng)導(dǎo)者挖掘的原理圖

用戶領(lǐng)導(dǎo)者挖掘算法的基本過程如下:

1) 對用戶領(lǐng)導(dǎo)者挖掘算法進(jìn)行問題建模及相關(guān)定義.

2) 計(jì)算用戶領(lǐng)導(dǎo)力,包括:用戶影響力的計(jì)算和用戶活躍度的計(jì)算.

3) 計(jì)算用戶中心性.

4) 將用戶領(lǐng)導(dǎo)力和用戶中心性結(jié)合,進(jìn)行用戶領(lǐng)導(dǎo)者的挖掘.

3 用戶領(lǐng)導(dǎo)者挖掘的計(jì)算方法

3.1 用戶影響力的計(jì)算

用戶影響力由粉絲對他的關(guān)注程度、粉絲的影響力、粉絲的規(guī)模及用戶發(fā)布的信息的覆蓋率決定.這里,對用戶u的影響力進(jìn)行計(jì)算.

3.1.1 粉絲對用戶的關(guān)注度

假設(shè)粉絲為v,粉絲對用戶的關(guān)注度包括粉絲對用戶轉(zhuǎn)發(fā)或發(fā)布的信息的轉(zhuǎn)發(fā)率、粉絲對用戶的評價(jià)率.粉絲v對用戶u的關(guān)注度為:

(1)

3.1.2 粉絲的影響力

粉絲影響力即用戶影響力,計(jì)算方法如下:

(2)

式中M,N,Q用于區(qū)分各個(gè)影響因素的重要性.

3.1.3 粉絲的規(guī)模

粉絲規(guī)模是由粉絲的數(shù)目占整個(gè)社交網(wǎng)絡(luò)用戶的比例與粉絲關(guān)注的用戶的數(shù)量綜合計(jì)算組成.粉絲v的規(guī)模為

(3)

3.1.4 用戶發(fā)布的信息的覆蓋率

用戶發(fā)布的信息的覆蓋率即為用戶發(fā)布的信息被轉(zhuǎn)發(fā)的數(shù)量占社交網(wǎng)絡(luò)用戶的數(shù)量的比例,比例越大,則覆蓋率越大.用戶發(fā)布的信息的覆蓋率為

(4)

其中,δhi用來標(biāo)志用戶h是否轉(zhuǎn)發(fā)過由用戶u發(fā)布的信息,如果轉(zhuǎn)發(fā)過,則δhi為1,否則為0.

上訴四個(gè)因素綜合計(jì)算得到用戶影響力進(jìn)行計(jì)算,用戶影響力的計(jì)算如公式(2).

3.2 用戶活躍度(UA)的計(jì)算

用戶活躍度由一段時(shí)間內(nèi)用戶轉(zhuǎn)發(fā)信息率、用戶發(fā)布信息率、用戶評論他人信息率決定.

3.2.1 用戶轉(zhuǎn)發(fā)信息率

用戶轉(zhuǎn)發(fā)信息率(RP)在ΔT時(shí)間內(nèi)用戶轉(zhuǎn)發(fā)的信息數(shù)占其接受到的信息的數(shù)量的比例.用戶轉(zhuǎn)發(fā)信息率為

(5)

3.2.2 用戶發(fā)布信息率

用戶發(fā)布信息率(RPU)是由在ΔT時(shí)間內(nèi)用戶發(fā)布的信息的數(shù)量與社交網(wǎng)網(wǎng)絡(luò)中信息的總數(shù)量組成.用戶發(fā)布信息率為

(6)

3.2.3 用戶評論他人信息率

用戶評價(jià)他人信息率(RE)是由在ΔT時(shí)間內(nèi)用戶評價(jià)他人信息的數(shù)量及社交網(wǎng)絡(luò)中評價(jià)的總數(shù)組成.用戶評價(jià)他人信息率為:

(7)

將以上三個(gè)因素結(jié)合,對用戶活躍度進(jìn)行計(jì)算.用戶活躍度為

UA(u)=γ×RP(u)ΔT+θ×RPU(u)ΔT+(1-γ-θ)×RE(u)ΔT.

(8)

其中,γ,θ是用來區(qū)分各個(gè)影響因素的重要性.

3.3 用戶領(lǐng)導(dǎo)力的計(jì)算

用戶領(lǐng)導(dǎo)力是由用戶影響力及用戶活躍度組成.用戶領(lǐng)導(dǎo)力的計(jì)算如下:

ULD(u)=λ×UI(u)+(1-λ)×UA(u).

(9)

其中,λ是為權(quán)重系數(shù),取值范圍為[0,1].

3.4 用戶領(lǐng)導(dǎo)者的挖掘

3.4.1 用戶中心性的計(jì)算

用戶中心性是由用戶在整個(gè)社會(huì)網(wǎng)絡(luò)中的中心性及用戶的位置的中心性組成的.用戶中心性的計(jì)算如下:

(10)

3.4.2 用戶領(lǐng)導(dǎo)者的挖掘

用戶領(lǐng)導(dǎo)者的判斷標(biāo)準(zhǔn)是用戶領(lǐng)導(dǎo)力高并且中心性明顯的用戶.用戶領(lǐng)導(dǎo)者的計(jì)算如下:

(11)

其中,ω是為權(quán)重系數(shù).選擇值排名前k個(gè)用戶為社交網(wǎng)絡(luò)的用戶領(lǐng)導(dǎo)者.

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

使用新浪微博作為實(shí)驗(yàn)數(shù)據(jù)源,驗(yàn)證本算法的正確性和準(zhǔn)確性.通過人工方法選取1 000個(gè)用戶作為數(shù)據(jù)集,數(shù)據(jù)集的具體情況如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)的特征

4.1 用戶影響力計(jì)算方法的評估

將提出的用戶影響力計(jì)算方法的準(zhǔn)確度和傳統(tǒng)的用戶影響力評估方法(TUIE)的準(zhǔn)確度進(jìn)行對比(圖2).并且從數(shù)據(jù)集中依次選取20,40,60,80,100人進(jìn)行對比,得出他們的平均準(zhǔn)確度進(jìn)行對比,使得實(shí)驗(yàn)結(jié)果更有說服力.通過對比實(shí)驗(yàn)結(jié)果,可以看到本文作者提出的計(jì)算方法更精確,并且穩(wěn)定性很高,準(zhǔn)確率高達(dá)98.5%,但是傳統(tǒng)的用戶影響力的評估方法穩(wěn)定性不高,得出的結(jié)果與實(shí)際用戶的影響力狀況不大符合.用戶影響力的準(zhǔn)確計(jì)算為下文計(jì)算用戶影響力提供了很好的基礎(chǔ).

圖2 不同用戶影響力評估方法的準(zhǔn)確度對比

4.2 用戶活躍度計(jì)算方法的評估

將本文作者提出的用戶活躍度計(jì)算方法的準(zhǔn)確度與直接根據(jù)單位時(shí)間內(nèi)用戶登錄頻度(UT)的準(zhǔn)確度及用戶單位時(shí)間內(nèi)發(fā)布和轉(zhuǎn)發(fā)微博的數(shù)量(The number of user published and propagated weibo in unit time,NPP)的準(zhǔn)確度進(jìn)行對比(圖3).同樣,從數(shù)據(jù)集中依次選取20,40,60,80,100人進(jìn)行對比,得出他們的平均準(zhǔn)確度進(jìn)行對比,使得實(shí)驗(yàn)結(jié)果更有說服力.通過對比實(shí)驗(yàn)結(jié)果,可見作者提出的計(jì)算方法準(zhǔn)確性高并且穩(wěn)定,適用于絕大部分的用戶.

圖3 不同用戶活躍度評估方法的準(zhǔn)確度對比

4.3 用戶中心性計(jì)算方法的評估

將作者提出的用戶中心性計(jì)算方法的準(zhǔn)確度與度中心性(DC)的準(zhǔn)確度進(jìn)行對比(圖4).從數(shù)據(jù)集中依次選取100,200,300,400人進(jìn)行對比,通過對比實(shí)驗(yàn)結(jié)果,可見作者提出的計(jì)算方法準(zhǔn)確性高并且穩(wěn)定,適用于絕大部分的用戶,而以往的根據(jù)用戶的度來確定用戶中心性的方法,準(zhǔn)確度很低.

圖4 不同用戶中心性評估方法的準(zhǔn)確度對比

4.4 用戶領(lǐng)導(dǎo)者挖掘算法的評估

將作者提出的用戶領(lǐng)導(dǎo)者挖掘算法的準(zhǔn)確度與傳統(tǒng)的挖掘影響力大的用戶(Traditional detection method of user′s influence,TDM)的準(zhǔn)確度進(jìn)行對比.隨著時(shí)間的變化,得出他們的平均準(zhǔn)確度并進(jìn)行對比,通過對比圖5(a)的實(shí)驗(yàn)結(jié)果,作者提出的計(jì)算方法準(zhǔn)確性高并且隨著時(shí)間的遷移穩(wěn)定性高,準(zhǔn)確度只會(huì)略微下降,適用于絕大部分的用戶,而傳統(tǒng)的研究方法雖然短期內(nèi)準(zhǔn)確性不是很低,但是隨著時(shí)間的遷移,準(zhǔn)確率會(huì)越來越低,找到的用戶領(lǐng)導(dǎo)者的準(zhǔn)確度明顯低于作者提出的挖掘方法.通過對比圖5(b)的實(shí)驗(yàn)結(jié)果,得出在抽取不同數(shù)目的用戶領(lǐng)導(dǎo)者時(shí),本方法優(yōu)于傳統(tǒng)的方法,并且即使抽取的規(guī)模擴(kuò)大,本方法的準(zhǔn)確度依舊很高,但是傳統(tǒng)的方法的準(zhǔn)確度會(huì)逐漸下降.

圖5 不同用戶領(lǐng)導(dǎo)者挖掘方法對比

5 總 結(jié)

本文作者基于用戶影響力提出了用戶領(lǐng)導(dǎo)者的挖掘算法,由以下幾個(gè)方面組成:1) 用戶領(lǐng)導(dǎo)者挖掘的問題建模及相關(guān)定義;2) 用戶領(lǐng)導(dǎo)力的計(jì)算,包括:用戶影響力和用戶活躍度的計(jì)算;3) 用戶中心性的計(jì)算;4) 挖掘社交網(wǎng)絡(luò)中用戶領(lǐng)導(dǎo)者.實(shí)驗(yàn)結(jié)果表明,本方法挖掘到的用戶領(lǐng)導(dǎo)者與實(shí)際情況相符.在未來的研究工作中,將針對實(shí)現(xiàn)社交網(wǎng)絡(luò)影響最大化進(jìn)行研究與拓展等.

[1] Li D,Xu Z M,Li S,et al.A survey on information diffusing in online social networks [J].Chinese Journal of Computers,2014,37(1):189-206.

[2] Zhou T,Fu Z Q,Wang B H.Epidemic dynamics on complex networks [J].Progress in Natural Science,2006,16(5):452-457.

[3] Qi C,Chen H C,Yu H T.Method of evaluating micro-blog users′ influence based on comprehensive analysis of user behavior [J].Application Research of Computers,2014,31(7):2004-2007.

[4] Zhai Z W,Xu H,Jia P F.Indentifying opinion leasers in BBS [C]//IEEE.2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology,Sydney:IEEE,2008.

[5] Lü L,Zhang Y C,Yeung C H,et al.Leaders in social networks the delicious case [J].PloS one,2011,6(6):e21202.

[6] Zhou W N,Fou R J,Liu L.Qos management and control of heterogeneous [M].Beijing:Electronic Industry Press,2009:3.

[7] Cha M,Haddadi H,Benevenuto F,et al.Measuring user influence in Twitter:the million follower fallacy [C]//IEEE.Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM 10),Washinton:IEEE,2010.

[8] Yang C C,Yu K F,Ye S R.New assessment method on influence of bloggers in community of Chinese microblog [J].Computer Engineering and Applications,2012,48(25):229-233.

[9] Xiao Y,Xu W,Zhang C.Influence Accessment Algorithm of Regional Influential Nodes in Online Social Networks [J].Microelectronics&Computer,2012,29(7):59-63.

[10] Ma J,Zhou G,Liu B,et al.Analysis of user influence in microblog based on individual attribute features [J].Application Research of Computers,2013,30(8):2483-2487.

[11] Li M,Wen H Y,Yang J,et al.Measuring user influence of micro-blog based on behavior weight [J].Computer Engineering and Applications,2014,50(17):130-133.

(責(zé)任編輯：包震宇,郁 慧)

A mining algorithm of user leader in social network

SONG Qianqian1, ZHANG Bo1, HU Sihui1, XU Qian1, PENG Ruxiang2

(1.College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China; 2.The Third Research Institute of Ministry of Public Security,Shanghai 201204,China)

Mining user leader in social network is an important issue for user influence management.In this paper,a user leader mining algorithm in social network based on user influence assessments is proposed,which comprises aspects as follows:firstly,the model of proposed algorithm and its related definitions are described formally;secondly,a user leadership degree evaluation method is presented based on user influence and user activeness calculation;and finally,the user leader mining algorithm is proposed based on two factors of user leadership degree and user centrality.Furthermore,the experimental results show the feasibility and effectiveness of our proposed algorithm.

social network; user leader mining; user influence; activeness; centrality

2015-06-08

國家自然科學(xué)基金(61572326,61103069,71171148);上海市教委科研創(chuàng)新項(xiàng)目(13YZ052);信息網(wǎng)絡(luò)安全公安部重點(diǎn)實(shí)驗(yàn)室開放課題項(xiàng)目(C14602);上海師范大學(xué)產(chǎn)學(xué)研項(xiàng)目(DCL201302)

彭如香,中國上海市浦東新區(qū)張江畢升路339號,公安部第三研究所,郵編:201204,E-mail:pengruxiang_2@163.com

TP 391

A

1000-5137(2016)05-0573-07

10.3969/J.ISSN.1000-5137.2016.05.010