社交网络影响力最大化的研究

《社交网络影响力最大化的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP391论文编号：102871616-S081学科分类号：081200硕士学位论文社交网络影响力最大化的研究研究生姓名王欢欢学科、专业安全科学与工程研究方向社交网络指导教师杨群副教授南京航空航天大学研究生院计算机科学与技术学院二Ο一六年一月NanjingUniversityofAeronauticsandAstronauticsTheGraduateSchoolCollegeofComputerScienceandTechnologyResearchonInfluenceMaximizationinSocialNetworksATh

2、esisinSecurityScienceandEngineeringByWangHuanhuanAdvisedbyAssociateProf.YangQunSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringJanuary,2016承诺书本人声明所呈交的硕士学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京航空航天大学或其他教育机构的

3、学位或证书而使用过的材料。本人授权南京航空航天大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）社交网络影响力最大化的研究摘要近几年来随着社交网络的兴起和快速发展，越来越多的学者开始研究社交网络，并挖掘其应用价值。社交网络影响力最大化问题成为社交网络研究领域的热点之一。社交网络影响力最大化是指在社交网络中找出一定数量影响力高的用户，使社交网络中受到他们影响的用户数量最多。该研究通常被应用于病毒营销。社交网络影响力最大化问题通常从传播模型和算法两个方

4、面进行研究。本文通过深入地分析近年来该问题的研究工作，对现有工作存在的不足进行改进，提出新的传播模型和算法，并通过在真实数据集上的实验验证了所提传播模型和算法的有效性。本文的主要研究工作体现在以下几个方面：(1)通过分析符号网络的特性和积极影响力在病毒营销中的重要性，提出了符号网络中积极影响力最大化问题。为了解决这个问题，首先在线性阈值模型上加入用户的态度和用户之间的关系，提出LT-A模型；随后证明影响力传播函数在该模型下具单调性和子模性，积极影响力最大化问题在该模型上是NP难问题，进而可以用贪婪算法解决该问题；本文最终提出LT-AGreedy算

5、法解决该问题；通过在真实社交网络数据集上的实验验证了所提模型和算法的有效性。(2)贪婪算法在解决积极影响力最大化问题时，时间效率低，不适用于大规模社交网络，在上述研究工作的基础上，本文根据三度影响力原则提出了基于三度影响力的启发式算法。三度影响力原则是指社交网络中用户的行为会影响到三度之内的朋友，超出这三度自身的影响力就会逐渐消失；它是影响力在社交网络上传播所遵循的规律，并且社交网络的规模越大三度影响力原则就会越明显。基于三度影响力的启发式算法就是根据这个特性选择出三度影响力大的节点作为种子节点的启发式算法。通过在真实社交网络数据集上的实验验证了

6、该启发式算法的运行时间比贪婪算法更短，且算法精度接近于贪婪算法。关键词：影响力最大化，积极影响力，符号社交网络，三度影响力I南京航空航天大学硕士学位论文ABSTRACTInrecentyears,astherisingandrapiddevelopmentofsocialnetworks,moreandmorescholarsareattractedtostudysocialnetworkstominetheiractualvalue.Thestudyofinfluencemaximizationinsocialnetworkshasbecome

7、oneofthehottopics.Influencemaximizationproblemistofindacertainnumberofhighinfluentialindividualstomaximizethenumberthatisaffectedbytheminsocialnetworks.Itisalwaysappliedinviralmarketing.Theinfluencemaximizationproblemisusuallystudiedfromtwoaspects,namelypropagationmodelandalg

8、orithm.Thispaperproposednewmodelsandalgorithms.Also,extensiveexperim