一种社交网络用户领导者挖掘算法

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

(1.上海师范大学 信息与机电工程学院,上海 200234;2.公安部第三研究所,上海 201204)



一种社交网络用户领导者挖掘算法

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

(1.上海师范大学 信息与机电工程学院,上海 200234;2.公安部第三研究所,上海 201204)

社交网络中的用户领导者挖掘是用户影响力分析的重要问题.提出一种基于用户影响力评估的社交网络用户领导者挖掘算法.首先,描述问题模型以及模型相关定义;其次,提出了基于用户影响力和用户活跃度计算的用户领导力评估方法;最后,依据用户领导力和用户中心度计算实现用户领导者的挖掘.实验印证了该方法对于社交网络挖掘用户领导者的可行性和有效性.

社交网络; 用户领导者挖掘; 用户影响力; 活跃度; 中心性

0 引 言

随着Facebook、Twitter等社交类网站的迅速发展[1],越来越多的研究开始关注信息传播[2]和用户作用分析[3],以实现社交网络用户影响力的有效评估,而在用户影响力评估的研究中,用户领导者挖掘是一个重要的课题.用户领导者即用户群体中领导力强的用户,用户领导者挖掘分析有益于增强社交网络信息的传播分析及控制等方面工作.

目前很多研究表明,用户影响力的研究是实现挖掘用户领导者的关键.Page等[4]基于用户间关系对用户进行PageRank排序实现分析用户影响力;吕琳媛等[5]基于PageRank算法的改进,提出了LeaderRank算法,通过添加公共节点实现连接网络中的全部节点,计算出用户的影响力;周文安等[6]基于用户的好友数量及质量提出了UserRank模型,分析用户影响力;Cha等[7]基于用户度数,用户在内容中被提及的次数,用户内容被转发或引用次数等指标分析用户影响力.然而,上述研究均未考虑用户对关注其用户的影响力不同的问题,未考虑到用户在单位时间内的活跃度问题,忽视了这些因素对于用户领导者挖掘的影响.

本文作者针对以往研究中存在的不足,提出了一种基于用户影响力评估的社交网络用户领导者挖掘方法.首先,描述问题模型以及模型相关定义;其次,提出了基于用户影响力和用户活跃度计算的用户领导力评估方法;最后,依据用户领导力和用户中心度计算实现用户领导者的挖掘.

第1节介绍了之前人们所做的一些相关工作与研究;第2节提出了社交网络用户领导者的挖掘算法;第3节介绍了在不同的数据集上进行的实验并且对实验结果进行了分析;第4节介绍了所做的主要工作以及在未来研究的重点.

1 相关工作

近年来,对用户影响力进行研究的方法很多,比较典型的有以下几种.

杨长春等[8]基于传统的PageRank算法的改进,提出了一种新的中文微博社区博主影响力的评估算法,通过研究微博中的微博博主的交互行为,构建微博社区网络模型,并且对网络特征进行统计和分析,基于PageRank算法,建立了新的评价指标,从而评估微博博主在微博社区中的影响力.

肖宇等[9]以人人网为例,对社交网络进行分析,提出了社交网络中用户区域影响力评估算法,该算法的主要思想是:用户在区域中的影响力与用户传播信息的意愿和社会传播能力有关,定量地对每个用户的传播影响力进行度量,从而得出用户在区域中的影响力.

马俊等[10]首先根据微博转发关系构建信息传播网,然后在该网络中从传播速度、范围和距离3个方面对信息传播特征进行定量分析.在此基础上,利用个人属性的统计数据对各传播特征进行回归分析,找出最能反映用户影响力的属性特征,进而利用其对用户影响力进行预测.

黎明等[11]提出一种基于行为权值的微博用户影响力度量算法.首先对网络用户的转发、评论和提及等用户行为进行分析,然后采用最小二乘支持向量机合理确定他人权值,建立传播影响力度量模型.

以上研究主要依赖于对用户影响力的研究大多数都是从用户的粉丝数、转发、评论、提及用户发布信息的用户数等方面对用户的影响力进行评估,尚未充分考虑用户对关注他的用户的影响力不同,以及用户在一段时间内的活跃度等重要因素.本文作者主要针对用户对关注他的用户影响力开展研究.

2 用户领导者挖掘算法模型

首先给出用户领导者挖掘算法模型(MULM)及其相关定义.

2.1 问题建模

通过引入图论方法对社交网络和用户领导者挖掘算法模型进行建模,如下所示:

2) 用户领导者挖掘算法模型:从社交网络用户集合中选取用户领导力及用户中心性强的前k个用户加入用户领导者集合(CUL),选取到的用户领导者可以表示为:u∈V并且u∈CUL.用户领导者和社交网络的关系可以表示为:CUL⊆V.

2.2 相关定义

为了便于MULM中的相关计算,有以下定义:

定义1 粉丝(Fans).粉丝是指社交网络中关注其他用户的用户,将关注者定义为该用户的粉丝.

定义2 用户影响力(UI).用户影响力是指用户对社交网络中其他用户的影响力,由粉丝对他的关注程度、粉丝的影响力及粉丝距离他的远近程度的规模等决定,并且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 用户影响力的计算

用户影响力由粉丝对他的关注程度、粉丝的影响力、粉丝的规模及用户发布的信息的覆盖率决定.这里,对用户u的影响力进行计算.

3.1.1 粉丝对用户的关注度

假设粉丝为v,粉丝对用户的关注度包括粉丝对用户转发或发布的信息的转发率、粉丝对用户的评价率.粉丝v对用户u的关注度为:

(1)

3.1.2 粉丝的影响力

粉丝影响力即用户影响力,计算方法如下:

(2)

式中M,N,Q用于区分各个影响因素的重要性.

3.1.3 粉丝的规模

粉丝规模是由粉丝的数目占整个社交网络用户的比例与粉丝关注的用户的数量综合计算组成.粉丝v的规模为

(3)

3.1.4 用户发布的信息的覆盖率

用户发布的信息的覆盖率即为用户发布的信息被转发的数量占社交网络用户的数量的比例,比例越大,则覆盖率越大.用户发布的信息的覆盖率为

(4)

其中,δhi用来标志用户h是否转发过由用户u发布的信息,如果转发过,则δhi为1,否则为0.

上诉四个因素综合计算得到用户影响力进行计算,用户影响力的计算如公式(2).

3.2 用户活跃度(UA)的计算

用户活跃度由一段时间内用户转发信息率、用户发布信息率、用户评论他人信息率决定.

3.2.1 用户转发信息率

用户转发信息率(RP)在ΔT时间内用户转发的信息数占其接受到的信息的数量的比例.用户转发信息率为

(5)

3.2.2 用户发布信息率

用户发布信息率(RPU)是由在ΔT时间内用户发布的信息的数量与社交网网络中信息的总数量组成.用户发布信息率为

(6)

3.2.3 用户评论他人信息率

用户评价他人信息率(RE)是由在ΔT时间内用户评价他人信息的数量及社交网络中评价的总数组成.用户评价他人信息率为:

(7)

将以上三个因素结合,对用户活跃度进行计算.用户活跃度为

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

(8)

其中,γ,θ是用来区分各个影响因素的重要性.

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 用户影响力计算方法的评估

将提出的用户影响力计算方法的准确度和传统的用户影响力评估方法(TUIE)的准确度进行对比(图2).并且从数据集中依次选取20,40,60,80,100人进行对比,得出他们的平均准确度进行对比,使得实验结果更有说服力.通过对比实验结果,可以看到本文作者提出的计算方法更精确,并且稳定性很高,准确率高达98.5%,但是传统的用户影响力的评估方法稳定性不高,得出的结果与实际用户的影响力状况不大符合.用户影响力的准确计算为下文计算用户影响力提供了很好的基础.

图2 不同用户影响力评估方法的准确度对比

4.2 用户活跃度计算方法的评估

将本文作者提出的用户活跃度计算方法的准确度与直接根据单位时间内用户登录频度(UT)的准确度及用户单位时间内发布和转发微博的数量(The number of user published and propagated weibo in unit time,NPP)的准确度进行对比(图3).同样,从数据集中依次选取20,40,60,80,100人进行对比,得出他们的平均准确度进行对比,使得实验结果更有说服力.通过对比实验结果,可见作者提出的计算方法准确性高并且稳定,适用于绝大部分的用户.

图3 不同用户活跃度评估方法的准确度对比

4.3 用户中心性计算方法的评估

将作者提出的用户中心性计算方法的准确度与度中心性(DC)的准确度进行对比(图4).从数据集中依次选取100,200,300,400人进行对比,通过对比实验结果,可见作者提出的计算方法准确性高并且稳定,适用于绝大部分的用户,而以往的根据用户的度来确定用户中心性的方法,准确度很低.

图4 不同用户中心性评估方法的准确度对比

4.4 用户领导者挖掘算法的评估

将作者提出的用户领导者挖掘算法的准确度与传统的挖掘影响力大的用户(Traditional detection method of user′s influence,TDM)的准确度进行对比.随着时间的变化,得出他们的平均准确度并进行对比,通过对比图5(a)的实验结果,作者提出的计算方法准确性高并且随着时间的迁移稳定性高,准确度只会略微下降,适用于绝大部分的用户,而传统的研究方法虽然短期内准确性不是很低,但是随着时间的迁移,准确率会越来越低,找到的用户领导者的准确度明显低于作者提出的挖掘方法.通过对比图5(b)的实验结果,得出在抽取不同数目的用户领导者时,本方法优于传统的方法,并且即使抽取的规模扩大,本方法的准确度依旧很高,但是传统的方法的准确度会逐渐下降.

图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);上海市教委科研创新项目(13YZ052);信息网络安全公安部重点实验室开放课题项目(C14602);上海师范大学产学研项目(DCL201302)

彭如香,中国上海市浦东新区张江毕升路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