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

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

?

一種社交網絡用戶領導者挖掘算法

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

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

社交網絡中的用戶領導者挖掘是用戶影響力分析的重要問題.提出一種基于用戶影響力評估的社交網絡用戶領導者挖掘算法.首先,描述問題模型以及模型相關定義;其次,提出了基于用戶影響力和用戶活躍度計算的用戶領導力評估方法;最后,依據用戶領導力和用戶中心度計算實現用戶領導者的挖掘.實驗印證了該方法對于社交網絡挖掘用戶領導者的可行性和有效性.

社交網絡; 用戶領導者挖掘; 用戶影響力; 活躍度; 中心性

0 引 言

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

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

本文作者針對以往研究中存在的不足,提出了一種基于用戶影響力評估的社交網絡用戶領導者挖掘方法.首先,描述問題模型以及模型相關定義;其次,提出了基于用戶影響力和用戶活躍度計算的用戶領導力評估方法;最后,依據用戶領導力和用戶中心度計算實現用戶領導者的挖掘.

第1節(jié)介紹了之前人們所做的一些相關工作與研究;第2節(jié)提出了社交網絡用戶領導者的挖掘算法;第3節(jié)介紹了在不同的數據集上進行的實驗并且對實驗結果進行了分析;第4節(jié)介紹了所做的主要工作以及在未來研究的重點.

1 相關工作

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

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

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

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

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

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

2 用戶領導者挖掘算法模型

首先給出用戶領導者挖掘算法模型(MULM)及其相關定義.

2.1 問題建模

通過引入圖論方法對社交網絡和用戶領導者挖掘算法模型進行建模,如下所示:

2) 用戶領導者挖掘算法模型:從社交網絡用戶集合中選取用戶領導力及用戶中心性強的前k個用戶加入用戶領導者集合(CUL),選取到的用戶領導者可以表示為:u∈V并且u∈CUL.用戶領導者和社交網絡的關系可以表示為:CUL?V.

2.2 相關定義

為了便于MULM中的相關計算,有以下定義:

定義1 粉絲(Fans).粉絲是指社交網絡中關注其他用戶的用戶,將關注者定義為該用戶的粉絲.

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

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

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

定義4 用戶領導力(ULD).用戶領導力是指在社交網絡中的用戶對其他用戶的領導能力,由用戶影響力和粉絲對其的關注程度組成.

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

定義6 用戶領導者(UL).用戶領導者就是在社交網絡中用戶領導力強并且中心性強的用戶,而用戶領導者的選取是根據社交網絡的需要選取的,不同的社交網絡選取用戶領導者的數目不同.可依據取值不同選取k個用戶領導者.

用戶領導者挖掘的原理如圖1所示.

圖1 用戶領導者挖掘的原理圖

用戶領導者挖掘算法的基本過程如下:

1) 對用戶領導者挖掘算法進行問題建模及相關定義.

2) 計算用戶領導力,包括:用戶影響力的計算和用戶活躍度的計算.

3) 計算用戶中心性.

4) 將用戶領導力和用戶中心性結合,進行用戶領導者的挖掘.

3 用戶領導者挖掘的計算方法

3.1 用戶影響力的計算

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

3.1.1 粉絲對用戶的關注度

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

(1)

3.1.2 粉絲的影響力

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

(2)

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

3.1.3 粉絲的規(guī)模

粉絲規(guī)模是由粉絲的數目占整個社交網絡用戶的比例與粉絲關注的用戶的數量綜合計算組成.粉絲v的規(guī)模為

(3)

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

用戶發(fā)布的信息的覆蓋率即為用戶發(fā)布的信息被轉發(fā)的數量占社交網絡用戶的數量的比例,比例越大,則覆蓋率越大.用戶發(fā)布的信息的覆蓋率為

(4)

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

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

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

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

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

用戶轉發(fā)信息率(RP)在ΔT時間內用戶轉發(fā)的信息數占其接受到的信息的數量的比例.用戶轉發(fā)信息率為

(5)

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

用戶發(fā)布信息率(RPU)是由在ΔT時間內用戶發(fā)布的信息的數量與社交網網絡中信息的總數量組成.用戶發(fā)布信息率為

(6)

3.2.3 用戶評論他人信息率

用戶評價他人信息率(RE)是由在ΔT時間內用戶評價他人信息的數量及社交網絡中評價的總數組成.用戶評價他人信息率為:

(7)

將以上三個因素結合,對用戶活躍度進行計算.用戶活躍度為

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

(8)

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

3.3 用戶領導力的計算

用戶領導力是由用戶影響力及用戶活躍度組成.用戶領導力的計算如下:

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

(9)

其中,λ是為權重系數,取值范圍為[0,1].

3.4 用戶領導者的挖掘

3.4.1 用戶中心性的計算

用戶中心性是由用戶在整個社會網絡中的中心性及用戶的位置的中心性組成的.用戶中心性的計算如下:

(10)

3.4.2 用戶領導者的挖掘

用戶領導者的判斷標準是用戶領導力高并且中心性明顯的用戶.用戶領導者的計算如下:

(11)

其中,ω是為權重系數.選擇值排名前k個用戶為社交網絡的用戶領導者.

4 實驗和結果分析

使用新浪微博作為實驗數據源,驗證本算法的正確性和準確性.通過人工方法選取1 000個用戶作為數據集,數據集的具體情況如表1所示.

表1 實驗數據的特征

4.1 用戶影響力計算方法的評估

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

圖2 不同用戶影響力評估方法的準確度對比

4.2 用戶活躍度計算方法的評估

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

圖3 不同用戶活躍度評估方法的準確度對比

4.3 用戶中心性計算方法的評估

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

圖4 不同用戶中心性評估方法的準確度對比

4.4 用戶領導者挖掘算法的評估

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

圖5 不同用戶領導者挖掘方法對比

5 總 結

本文作者基于用戶影響力提出了用戶領導者的挖掘算法,由以下幾個方面組成:1) 用戶領導者挖掘的問題建模及相關定義;2) 用戶領導力的計算,包括:用戶影響力和用戶活躍度的計算;3) 用戶中心性的計算;4) 挖掘社交網絡中用戶領導者.實驗結果表明,本方法挖掘到的用戶領導者與實際情況相符.在未來的研究工作中,將針對實現社交網絡影響最大化進行研究與拓展等.

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

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

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

國家自然科學基金(61572326,61103069,71171148);上海市教委科研創(chuàng)新項目(13YZ052);信息網絡安全公安部重點實驗室開放課題項目(C14602);上海師范大學產學研項目(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