基于多学习因子粒子群算法的微博用户影响力分析-张硕.pdf

《基于多学习因子粒子群算法的微博用户影响力分析-张硕.pdf》由会员分享，可在线阅读，更多相关《基于多学习因子粒子群算法的微博用户影响力分析-张硕.pdf（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、基于多学习因子粒子群算法的微博用户影响力分析张硕，杨一平，武装(首都经济贸易大学信息学院，北京100070)摘要：分析了用户与其所在网络社团之间的关系，将岛屿模型的思想应用于标准粒子群算法的改进，提出了一种多学习因子粒子群算法(MPSO)。该算法综合考量了用户自身属性和社团关系网络特性两种影响因子，克服了网络水军和僵尸粉的干扰，同时这种改进的粒子群算法使得粒子在进化过程后期更具多样性，避免陷入局部最优。最后通过与Page Rank算法、BehaviorRelationship Rank算法进行对比，充分验证了MPSO算法的准确性以及可靠性。关键词：用户影响力；多学习因子粒子群算法；岛屿模型；社

2、交网络DOI：1013956jss1001840920171030中图分类号：TP391 文献标识码：A 文章编号：10018409(2017)10014005Analysis of Microblog UsersInfluenceBased on M PSO AlgorithmZHANG Shuo，YANG Yiping，WU Zhuang(School of Information，Capital University of Economics and B淞iness，Beijing 100070)Abstract：7rhis paper considerates the relation

3、ship between user and social network，and proposes MPSO algorithm whichapplies island model to the improvement of standard particle SWalTU algorithmThe algorithm considerates the informationfrom user attribute and social network factorsso it can overcome the influenee of artificial followersAt the sa

4、nle timeMP-SO algorithm increases the diversity of particles and avoids to fall into local optimumThenit compares the BehaviorRelationship Rank algorithmPage Rank algorithm诵tIl MPSO algorithm to prove the accuracy and reliability of itKey words：user influence；MPSO；island model；social network1 引言微博是近

5、年来一种新兴的社交网络平台，用户可以通过网页、手机以及其他通讯设备等登录微博并对信息进行浏览和分享，通常字数在一百四十字以内。Berger曾指出，社会分享内容的扩散并不是一个随机过程而是取决于其自身的“传播性”。在微博平台上这一现象则更为突出，获得高关注度的博主往往会在微博信息的传播中起到向导的作用，甚至可以决定热点话题的产生以及扩散范围。因此，研究微博用户影响力不但对于微博信息的分析和挖掘有着至关重要的作用，还可以在一定程度上帮助有关部门应对突发事件的产生。最初，Huberman等用Twitter用户的粉丝数来衡量其影响力的大小，随后关于社交网络平台上用户影响力的研究则吸引了大批学者的关注心

6、-。在国外的研究中，很多人将传统的PageRank算法应用于网络平台上用户影响力的研究，但由于该算法本身存在弊端，因此只能描述出用户之间的关注关系而忽略了账户的自身属性p。在此基础上，研究者们结合社交网络的特点，将情感分析、文本分析等方法应用于Page Rank算法的改进。Meeyoung Cha L4 J提出了一种基于用户行为和用户关系的BehaviorRelationship Rank算法(BRR)，该算法包含入度、博文被转发以及博主被“”3种用户行为，然而这种方法刻画的是用户在过去某个时刻的影响力而不具备对当前或是未来某时刻影响大小进行度量的能力，因此不具备实用性。Chen和Kimura

7、将研究方向转向信息的传播和扩散过程上，用贪婪算法进行仿真模拟，最终将问题转化为如何挑选关键节点使得信息传播可以实现影响力最大化”冉1。Weng则将微博平台看做一个复杂的网络系统，对不同信息主体下收稿日期：20160902 基金项目：国家社会科学基金项目(16BGLl45)；北京市社会科学基金项目(14SHB015)；北京市教育委员会科学研究计划基金项目(SM201410038013)作者简介：张硕(1992一)，女，北京人，硕士研究生，研究方向为智能算法、信息经济学；杨一平(1954一)，男，教授、博士生导师，研究方向为管理信息系统、信息经济学；武装(1970一)，男，副教授、硕士生导师，研究

8、方向为智能算法、图形图像与软件工程。140万方数据信息的传播路径进行分析，通过实验证明了在不同的信息类别下草根用户拥有比大V用户更强的影响能力u1。在国内的研究中，石磊等人综合考虑了用户粉丝数、关注数、博文数等，将活跃度指数引入用户影响力计算。唐杰和吴斌等人则建立了不同主题以及不同邻域下用户影响力传播模型，以此研究不同主题内容下用户影响力的大小归”J。而后，随着网络的进一步发展，研究则集中于应对微博中大批出现的水军和僵尸粉的干扰。Dejin等用PR值表示用户节点的入度，构建了User Active Rank模型并引入用户活跃度和博文实时性等重要参数来衡量用户节点的影响力大小，该方法的弊端是会倾

9、向于发博文数较多的用户节点111。Eytan Bakshy认为口碑信息的传播存在级联关系，因此为了有效解决僵尸粉的影响，他从最受欢迎节点的URL开始，滚动追踪一系列跟随者的URL地址，直至传播过程终止2|。但是该方法计算过程复杂，效率不高，最重要的是忽略了用户节点本身的特性。与上述工作相比，本文的研究在用户粉丝数、关注数和博文数等广泛被研究的因素之外，将用户所在的社团关系网络特性引入了影响力的计算模型之中，应用岛屿模型的思想提出了一种基于多学习因子的粒子群算法(MPSO)。该算法综合考量了用户自身属性以及所在的关系网络特性，克服了水军和僵尸粉的干扰，同时这种改进的粒子群算法增加了粒子在后期进化

10、过程中的多样性，避免陷入局部最优。最后通过与Page Rank算法、BRR算法进行对比，证明了MPSO算法的准确性和高效性。2相关研究以及特征属性提取21 Page Rank算法Page Rank算法是上世纪末由Google创始人提出的，该算法的主要思想是将用户浏览网页的行为模型化，进而利用网页之间的链接结构来确定该网页的重要程度1。由于社交网络中用户的关注和被关注关系与网页中的链入和链出关系非常类似，因此大量的研究者们将PageRank算法应用到在线社会网络的研究中，借此评估某用户节点在消息传播网络中的重要程度。其计算公式为：一PaeeRankfP、PageRank(Pf)。d+(1一d)专

11、雨亨上(1)PE村(P) uj式(1)中，P表示单个用户，M(Pi)为该用户的入度，L(P。)为该用户的出度，d为阻尼系数，表示该用户随机关注其他用户的概率。但是，在上述计算方法中仅仅是将这些用户节点比拟为静态的网页，并没有考虑其背后所具有的关系网络特性。主要忽视了以下3个方面：(1)节点间的信息传播方式；(2)节点之间存在的弱链接关系；(3)社交网络中邓巴数字的影响。针对Page Rank算法的不足，学者们做了大量的改进。然而这些研究中大都将用户行为作为重要考虑的方面，很少去关注导致这些用户行为发生的一些社会特性。为了克服之前研究工作的不足，本文以用户为切入点，同时对用户自身属性以及所在的社

12、团关系网络特性进行分析，将2种影响因子引入模型的计算，进而度量用户的信息传播能力。22微博用户影响力特征提取221用户自身属性微博具有实时性、自主性以及共享性等特点，每天都有大量的用户在微博平台上参与热点话题的讨论。用户登录微博之后不仅可以对外发布信息还可以浏览来自于其他用户的信息，当看到感兴趣的话题时，用户通常会根据认知水平挑选出自认为有价值的内容进行分享和转发，同时作为信息源头的博主也会因此获得更多的关注。在整个过程中，大V用户的分享、评论等行为对信息的传播起到至关重要的影响。研究发现，微博账户的粉丝数、关注数以及互粉数最能体现单个微博用户的账户状态心。31“。因此，为了评估微博平台上用户

13、影响力的大小，定义声望值P如下：r、上1P=坦(坐掣)(2)。Vg(肛)+1上式中，N，代表用户斗的粉丝数(即肛的入度)，N；代表用户肛的关注数(即斗的出度)。222社团密度趋同性是社会网络最基础的特征之一，指的是处于不同环境下的角色之间会相互影响、相互借鉴，直至趋向一致。Singla等在真实社会网络中进行了大规模的趋同性实验，其实验结果验证了大规模在线社会网络上趋同性的存在H“。通过提取微博用户的相关信息，借助网络可视化分析工具PKUVIS构建信息传播网络结构图(如图1所示)。从图1可以看出，信息完全围绕着几个关键用户节点(粉丝数10万以上)进行传播，很少在离散的节点上聚集。雹图1信息传播网

14、络结构图将网络社团结构进行划分，设节点v。所属的网络社团编号为Or，节点v；所属的网络社团编号为叮，当盯。=叮；时，8(叮；，盯，)=l。则社团密度函数Q钊可以定义为： 厶LQ 2孺1乏ai一寄)8(Or) (3)式(3)中，a。表示网络邻接矩阵中的元素，M=a。2代表网络社团中边的数目，k，和k分别代表节点v；、v；的度。若Q的函数值接近1，表明社团内部结构高度紧密很多的社会学研究者们已经证明了在社交网络中没有直接联系的节点同样会对整个社交网络中信息传播起到一定作用，其中比较著名的例子有三元闭包的概念。邓巴数字是英国牛津大学人类学家罗宾邓巴提出，指人类的智力允许人类拥有稳定的社交网络的人数为

15、150人左右。141-万方数据链接。在实际应用中，Q E03，07。3用户影响力度量模型31标准粒子群算法标准粒子群算法在基本公式中引入了惯性权重因子用来平衡全局与局部搜索能力，粒子的速度与位置更新公式如下“：秽f(n+1)=刚l(n)+clrl(P。一咒。(t) +C 2r2(P一戈：(n) (4)戈。(n+1)=算f(n)+口f(n+1) (5)其中，i=1，2，3，in代表了不同的粒子，(I)(0，1)用来对粒子当前速度进行调控，c，c：为大于零的学习因子，r，和r：为介于0，1之间服从均匀分布的随机数，n为迭代次数，xi(n)为粒子当前位置，P，为粒子自身历史最佳位置，P。为邻域历史最

16、佳位置。站在社会学的角度，式(4)的第一部分是“记忆”项，表示粒子当前速度对之前速度的继承；第二部分是“自身认知”项，代表微粒根据自身经验能够及时做出自我调整的能力；第三部分是“群体认知”项，代表微粒对社会经验的认知能力，同时这也反映出粒子之间是存在着信息共享行为的，而粒子也正是凭借自身认知和群体认知得出来的结果来为下一步行动做出决策。32 多学习因子粒子群算法(MPSO)由于标准粒子群算法在进化过程中仅仅对群体以及自身的最佳适应度值进行考量，因而粒子在进化过程后期缺乏多样性、收敛精度低、容易陷入局部最优。本文将岛屿模型的思想应用于标准PS0算法的改进，提出了一种多学习因子粒子群算法(MPS0

17、)。该算法的主要思想如下，根据整个种群中的粒子数目将其均分为1T1个子群体，并在其中任选一个作为主群，在每一个子群都独立进行搜索，待各个子群的搜索结束之后再将计算出来的最佳适应度值汇报到主群中。整个过程中，只采取单向的传播机制，即主群并不反向将汇总而来的最佳适应度值广播给各个子群。重新定义粒子的状态更新方程如下：口；(n+1)=伽f(n)+妒lClyl(P。一zi(n)+9 2c2y2(P z一菇。(n)+C zy 3(P，一戈i(n) (6)菇i(n+1)=戈。(n)+移i(n+1) (7)上式中，P；为单个粒子自身最佳位置，P。为各子群中最佳粒子适应度的值，P。为主群中最佳粒子适应度的值，

18、c，C 2c，为大于零的学习因子，rlr：1，为介于0，1之问服从均匀分布的随机数。P，和P：为影响因子，用来描述个体以及各子群内最佳适应度值对v带来的影响。根据上一节中对微博用户影响力构成因素的分析，可用P，表示用户的声望值，p：表示用户所在的社团密度，定义： 妒，=lg(粼)(8)og Lp，1。1妒：2删J-X。(。F一菥)8(0-川 (9)将上式带入式(6)中可得：“n+1)：制；(n)+lg(黜)cly。(p。飞2gt,xj。1(n)+芴1；(。F一希)8(0-j)c：yz(旷戈；n)142+C 3T 3(P。一z；(n) (10)因此整个算法的速度更新公式可表示为：口。(g+1)=

19、T1+r2+r3+L (11)其中，T，代表粒子对之前速度的继承，T：代表粒子自身学习能力，T，代表粒子在群体间的交互学习能力，T。代表粒子向全局最佳适应度值进行学习的能力。这样一来，可以使得粒子在进化过程后期依然保持多样性，在不陷入局部最优的同时又能一直朝着全局最优点的方向移动。在整个搜索过程中本文将平台上的用户节点视为单个粒子，因此粒子寻优的过程也就可以视为寻找关键影响力用户节点的过程。33 MPSO算法的参数分析为了验证算法的正确性，首先对其进行收敛性分析。荔01lClll 2 m1，盯2c 2Y2 2 in2，c 3y 32 iil3，In。inl+m2+in，则式(6)和式(7)可以

20、改写成如下形式：口；(t+1)=删(t)+m1P(t)+m2P z(t)+m 3P。(t)一眦。(t) (12)戈；(t+1)=OYY。(t)+mIP；(t)+m2Pf(t)+m 3P，(t)+(1一m)x。(t) (13)转换为向量表达式如下：vi(t+1)，H：。二跏寰】+(乏乏：|)rpl(t)P。(f)l (14)Lp，(t)_J另设：2匕1三，) (15)yk乏习 ，上式收敛的充分必要条件是I入l10时，应满足：一22一mt+、亿F孑Fi222一m一vTF=；陌2此时，m无解。(18)(19)当(2一m 7)240时，求得0m 74，因此0叮1c1y1+132C 272+c 3y34

21、。因为y1，12，y 3均为0，1之间的随机数，所以有：0妒1C1+9 2C 2+c 3y 34 (20)综上所述，为了保证公式的平衡性和算法的收敛性，算法中C。，c：和C，均取常数值2，影响因子的取值满足P1+P 2=1。4实验验证41数据集利用新浪开放的API接口和数据采集器获取了10000名用户在2016年7月27 13至2016年8月27 13期间的相关数据，这些数据主要包括账户自身属性，好友关万方数据系，转发微博数以及被转发微博数等。这段时间正好包含了“里约奥运热”，所以微博平台上用户的活跃度相对较高。在计算过程中，首先对各指标做了归一化处理，并利用层次分析法给用户自身属性和社团密度

22、属性两种影响因子分配权重，结果如表1所示。表1指标权重之后，本文分别用Page Rank算法、BRR算法和MPSO算法对微博用户影响力进行计算，以此证明该改进算法的准确性以及可靠性。42用户影响力评价标准相较于其他传统的社交网络而言，微博社区的交流网络更具多样性。因此，如若按影响力的大小程度对微博用户进行区分则不能得出准确的评估结果。借助英国剑桥大学DrMatthew Johnson基于c#平台编写的SVM模型，取5000名微博用户作为训练样本，将用户节点分为AD四个等级。影响力Fe(n)的值由前n个用户的相对影响力度f(i)共同构成，计算公式如下所示：Fe(n)2(凡+1一i状i)n(n+2

23、)2(21)其中，f(i)在不同级别下的取值如表2所示(处于A级与B级的用户可视为关键影响力用户)。表2 f(i)在不同影响力级别下的取值影响力等级 f(i)A级B级C级D级l06O20由于实验数据较多且微博用户影响力存在较大差异，因此重点研究迭代之后排在前40名的用户，然后根据分析结果确定算法的可行性和准确性。43实验结果分析对于处理后的数据，分别用Page Rank算法、BRR算法和MPSO算法进行计算。为了简化运算结果，仅将排名在前40位的用户数据在表3中列出。表3不同算法下用户影响力排序从表3中可以看出，MPSO算法相较PR算法的影响力用户数多了6个，相较BPR的影响力用户数多了10个

24、，相对提高率分别为231和455，性能增加比较明显。接着，本文借用Matthew Johnson教授提出的实验评估标准来进行计算，其统计结果如表4所示。表4用户影响力值Fe(n)的比较洳=坠鼍等屿坠鼍岽虹为了能更清楚看到不同算法对应的Fe(n)值，绘制了图2。憎村刮O 20 30 40用户排名口PR囟BPRMPSO图2不同算法下Fe(n)值对比从图2中可以看到各算法的Fe(n)值均随着n的增加而减小，且在任意排名阶段MPSO算法的准确性都优于其他二者。由于随着n的增加，3种算法的影响力值会逐渐趋于一致，因此这也说明了MPSO算法在识别排名相对靠前的关键用户节点上更具有效性。5结论用户影响力分析

25、是当前微博社区研究领域中的一个热点，本文将岛屿模型的思想应用于标准粒子群的改进，提出了一种基于多学习因子的粒子群算法(MPSO)。该算法综合考量了用户自身属性以及关系网络特性，克服了水军和僵尸粉的干扰，同时这种改进的粒子群算法增加了粒子在后期进化过程中的多样性避免陷入局部最优。最后通过与Page Rank算法、BRR算法进行对比，证明了MPSO算法的可靠性和有效性。在接下来的工作当中，本文将着重从2个方面入手：一方面，借助相关计算机技术分析用户的浏览器日志记录，更多地获取用户之间的交互关系，分析其在社团之中的交互行为。另一方面，本文认为在算法的后续改进中应该进一步与博文内容等相结合，通过引入语

26、义信息分析的方法，不但能更加准确地分析用户节点的影响力大小，也能帮助有关部门预测舆情话题的出现，针对突发事件尽早做出预案准备。参考文献：1Berger J，Milkman K LEmotion and Virality：What Makes OnlineContent Go Viral?JGfk Marketing Intelligence Review，2014，5(1)：1823-143鲫如o万方数据2Huberman B A，Romero D M，Wu FSocial Networks that Matter：Twitter under the MicroscopeJFimt Monda

27、y，2008，14(1)：20093Brin S，Page LThe Anatomy of a Largescale Hypertextual WebSearch EngineJComputer Networks and ISDN Systems1998，30(17)：1071174Cha M，Haddadi H，Benevenuto F，et a1Measuring User Influencein Twitter：The Million Follower FallacycIcwsm 10：International AAAI Conference on WeblogsSocial20155

28、Chen W，Wang C，Wang YScalable Influence Maximization forPrevalent Viral Marketing in Largescale Social NetworksCACMSIGKDD International Conference on Knowledge Discovery and DataMining，Washington，Dc，Usa，July，2010102910386Kimura M，Saito K，Nakano R，et a1Extracting Influential Nodeson a Social Network f

29、or Information DiffusionJData Mining andKnowledge Discovery，2010，20(1)：70977Weng J，LimE P，Jiang J，et a1TwitterRank：FindingTopicsen-sitive Influential TwitterersCACM International Conference onWeb Search and Data MiningACM，20102612708石磊，张聪，卫琳引入活跃指数的微博用户排名机制J小型微型计算机系统，2012，33(1)：1101149Sun J，Tang JMod

30、els and Algorithms for Social Influence AnalysisJSocial Network Data Analyties，2013：77577610刘金龙，吴斌，陈震，等基于领域划分的微博用户影响力分析J计算机科学，2015，42(5)：42461112131415161718ZhaoDeiinRosson M BHow and Why People Twitter：TheRole that Micro。blogging Plays in Informal Communication at WorkcProceedings of the ACM 2009 I

31、nternational Conference onSupporting Group Work ACM2009：243252Bakshy EHofman J M，Mason W A，et a1EveryoneS an Influencer：Quantifying Influence on TwittercACM InternationalConference on Web SearchData Mining2015：6574姚茜，h彦芳基于影响力研究的微博营销模式探析J经济问题探索，2011(12)：117121张进，刘琰，罗军勇，等基于特征分析的微博炒作账户识别方法J计算机工程，2015，4

32、1(4)：4854Parag，Singla，Matthew，et a1Yes，There Is a Correlation：FromSocial Networks to Personal Behavior on the WebCIntemation-al Conference on World Wide WebACM2008：16271628Girvan MNewman M E JCommunity Structure in Social and Biotogical NetworksJProceedings of the National Academy of Sci-ences of th

33、e United States of America，2002，99(12)：78217826Shi Y，Eberhart R CParticle Swarm Optimization with Fuzzy Adaptire Inertia WeightProcZWorkshop on Particle Swarm Optimization，2001578580陈小飞，王铁彤，冯小军一种基于网页质量的Page Rank算法改进J计算机研究与发展，2009，46(4)：381387(责任编辑：石琳娜)超额收益分配中应考虑分配结果对投资者努力水平的影 7K。ooaew N，Chiara M A M

34、odeli“g Cove”me呲R“8“。Gu“m。88节：，妻塑!皂毫銮望竞曼毪黧耋熙妻絮煮黧：娶等 in Privately BuilTra，nsp：or。ta。t：io，n：Projects：ALJ J-Irailsport,。ulJ,瞰出趟“咖8如印础套：妻虿孝拿票要现奎孽堡璺些篓皇蹩竺lj婴要I仝耋堑8赵立力，游琦高速公B”O“T项10目3调l节yl基金决策机制研究J代理理论，构建PPP交通项目超额收益最优分配模型，在信 。看i至茹聂，盂：27(3)：矗：8：5：。息不对称的条件下给出最优超额收益比例，在最大化公共 9高颖，张水波，冯卓PPP项目运营期间需求量下降情形下的补参考文献：

35、 i iVassallo J MTraffi。Risk Midgati“in Hi曲”ay Concession Pro一1达霖格里姆赛ppp：i输：公共服务中的政府和社会资本合作 J。出：Th8E3P8li8“。8 0fchil。JJo“al。fTran8P。n Economics2圣言青，喻刚，邴兴国PPP项目融资模式风险分担研究J软 12郭健公路基础设施PPP项目交通量风险分担策略研究J3 3陈晓红，郭佩含基于实物期权的PPP项目政府补偿机制研究 13Wa“g L，Liu JE7al“砒i”ofthe ExcessRevenue shari“g Ratioi“to Risk ControlinPublicPrivate PartnershipsMspringerBerlin 14蒲勇健建立在行为经济学理论基础上的委托一代理模型：物2010，14(2)：139155。pers，2008，1(1)：355384144万方数据