基于微博网络的影响力最大化算法(3)

　　定义微博网络为G=〈V，E〉，S为包含K个节点的种子集合，sv为节点v一次扩散得到的传播范围，IS（S）为种子集S最终的影响范围，则基于ELTM的贪婪算法如下所示。

　　3实验仿真

　　3.1数据集描述

　　为了验证本文提出的微博影响力最大化算法的有效性，本文选取了新浪微博中的“微群”数据进行实验验证。微群是微博群的简称，能够聚合具有相同爱好或者相同标签的用户，将所有与之相应的话题全部聚拢在微群里面。因此，同一微群里的微博用户具有较高的聚合度和活跃程度，适合作为影响力分析的数据源。

　　本文首先利用Web爬虫技术采集了某一微群内所有成员的用户ID，之后利用新浪提供的API接口采集对应ID的相关数据，具体包括：

　　1）各用户ID对应的用户信息，包括用户名称、关注数、粉丝数、发布微博数等；

　　2）用户的关注关系，包括用户所关注的其他用户ID，仅限制在收集该微群内的用户；

　　3）用户的转发及评论信息，包括被转发的消息ID，被转发及评论的用户ID仅限制在收集该微群内的用户。

　　基于采集到的数据，构建了微群中的关注网络，数据集中包含了3694个用户节点以及14624条关注关系组成的边。

　　3.2对比算法

　　为了验证本文提出的GABE在微博网络影响力最大化问题上的有效性，采用以下三种常用影响力最大化算法或微博影响力度量方法作为对照：

　　1）KKT算法：Kemple和Kleinberg提出的一种自然的爬山贪心算法，算法的每一步都选择当前最有影响力的节点放入种子集合中，将这种算法作用到线性阈值模型中就形成了当前在社会网络最大化问题中常用到的KKT算法。

　　2）PageRank算法：PageRank算法是常用的影响力度量算法，其影响力的分配依据节点的度数大小。

　　3）粉丝数排名（Followers）：依据用户的粉丝数目对用户影响力进行排序。

　　3.3实验结果

　　在传统的影响力最大化算法研究中，挖掘到的TopK节点只在影响力传播模型上仿真其覆盖效果，本文将评估GABE及其他对比算法挖掘到的TopK节点在真实网络中的传播覆盖效果，以此验证GABE的有效性。

　　4结语

　　为解决微博网络中影响力最大化这一问题，本文首先提出微博用户影响力度量的WIR算法，构建了符合微博影响力传播特征的扩展的线性阈值模型，进而建立了基于微博网络的影响力最大化算法GABE。在真实微博数据集中的实验结果表明，GABE可以较好地解决现有微博影响力排序结果中的范围重叠问题，并且相比常用TopK节点挖掘算法在微博网络上的影响范围上有很好的扩大。后续将在GABE的时间复杂度优化方面做进一步研究，以实现效率更高的微博网络影响力最大化算法。

　　参考文献：

　　[1]RICHARDSONM，DOMINGOSP.Miningknowledgesharingsitesforviralmarketings[C]//KDD02：ProceedingsoftheEighthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork：ACM，2002：61-70.

　　[2]KEMPED，KLEINBERGJ，TARDOS.Maximizingthespreadofinfluencethroughasocialnetworks[C]//KDD03：ProceedingsoftheninthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork：ACM，2003：137-146.

　　[3]LESKOVECJ，KRAUSEA，GUESTRINC，etal.Costeffectiveoutbreakdetectioninnetworkss[C]//KDD07：Proceedingsofthe13thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining.NewYork：ACM，2007：420-429.

　　[4]CHENW，WANGC，WANGYJ.Scalableinfluencemaximizationforprevalentviralmarketinginlargescalesocialnetwork[C]//KDD10：Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork：ACM，2010：807-816.

　　[5]RAMASURIN，YADATIN.NARAYANAMR，NARAHARIY.Ashapleyvaluebasedapproachtodiscoverinfluentialnodesinsocialnetworks[J].IEEETransactionsonAutomationScienceandEngineering，2011，8（1）：130-147.

　　[6]田家堂，王轶彤，冯小军.一种新型的社会网络影响最大化算法[J].计算机学报，2011，34（10）：1956-1964.

　　[7]BAKSHYE，HOFMANJM，MASONWA，etal.Everyonesaninfluencer：quantifyinginfluenceontwitter[C]//WSDM11：ProceedingsoftheFourthACMInternationalConferenceonWebSearchandDataMining.NewYork：ACM，2011：65-74.

　　[8]KWAKH，LEEC，PARKH，etal.Whatistwitter，asocialnetworkoranewsmedia？[C]//WWW10：Proceedingsofthe19thInternationalConferenceonWorldWideWeb.NewYork：ACM，2010：591-600.

　　[9]CHAM，HADDADIH，BENEVENUTOF，etal.Measuringuserinfluenceintwitter：themillionfollowerfallacy[C]//Proceedingsofthe4thInternationalAAAIConferenceonWeblogsandSocialMedia.Washington，DC：AAAI，2010：10-17.

　　[10]郭浩，陆余良，王宇，等.基于信息传播的微博用户影响力度量[J].山东大学学报：理学版，2012，47（5）：1-6.

　　[11]WENGJ，LIMEP，JIANGJ，etal.TwitterRank：findingtopicsensitiveinfluentialtwitterers[C]//WSDM10：Proceedingsofthe3rdACMInternationalConferenceonWebSearchandDataMining.NewYork：ACM，2010：261-270.

　　http：//ink.library.smu.edu.sg/cgi/viewcontent.cgi？article=1503&context=sis_research

　　[12]杨长春，俞克非，叶施仁，等.一种新的中文微博社区博主影响力的评估方法[J].计算机工程与应用，2012，38（25）：229-233.