基于期望分析的社会网络影响最大化问题的研究

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

1、南京大学硕士学位论文基于期望分析的社会网络影响最大化问题的研究申请人：张尧学号：MG0833060专业：计算机软件与理论研究方向：分布式计算与并行处理指导教师：陈道蓄教授顾庆教授2011年5月AStudyofExpectationbasedInfluenceMaximizationProbleminSocialNetworksByZHANGYaoAthesisSubmittedtothefacultyofgraduatestudiesinpartialfulfillmentoftherequirementsf

2、orthedegreeofMASTEROFENGINEERINGInComputerSoftwareandTheorySupervisedbyProf．CHENDaoxu&GUQingDepartmentofComputerScienceandTechnologyNanjingUniversityMay，2011Nanjing，P．R．China南京大学硕士学位论文摘要盐笠垫丛生鱼墨逾专业2QQ墨级硕士生姓名：堂整指导教师(姓名、职称)：睦道萱耋咝亟迭整撞摘要近年来，随着社交网络、微博等新兴网络应用的普及，因

3、特网中的信息传播规模呈现指数级增长。在海量的数据中，如何找到网络里最有影响力的节点成了数据挖掘领域和社会网络分析领域的热点问题。影响最大化问题(influencemaximizationproblem)致力于解决此类问题：在一个给定的网络中，根据某种信息传播模型，找出一个给定节点的集合，通过这个集合中的节点向其他节点施加影响，使原本只存在于这个集合节点上的信息可以传播到尽可能多的节点上。该问题可以应用于病毒研究、网络应用推广、市场分析等诸多领域。本文提出了一个基于期望的评价影响力函数的方法，相比于传统的蒙特卡

4、洛方法，该方法不需要进行大量的随机模拟。基于此，本文设计了两种可针对不同传播模型的算法来解决影响力最大化问题，并且讨论了两种算法的效率，最后通过在大规模现实网络上的实验，验证了本文算法的有效性。本文的主要贡献如下：1、综述了社会网络信息传播和影响最大化问题的相关研究背景。本文首先介绍了社会网络的基本概念和性质，然后总结了社会网络中常见的信息传播模型，最后引出影响最大化问题，并讨论了学者们解决该问题的相关工作。2、提出了一种评价影响力的期望值函数。针对蒙特卡洛随机模型的不足，本文首次提出了基于期望的影响力评价函

5、数，并给出了集合影响力和集合边际收益的期望表示。在此基础上，提出了一种解决影响最大化问题的框架。3、设计了两种基于期望的影响最大化算法。本文介绍了两种基于期望的影响最大化算法：贪婪广度优先的影响最大化算法和期望估计的影响最大化算法。这两种方法以贪婪算法为基础，并通过一定的理论推导证明了方法的有效性，给出了两种算法的南京大学硕士学位论文摘要复杂度。4、通过实际的大规模社会网络数据，评价了本文算法的效果。本文在多个科学家合作网络上运行提出的两类基于期望的算法，通过影响力函数和运行时间两个指标评价算法效果。在评价过

6、程中，与多种启发式算法和贪婪算法比较，通过实验验证算法的有效性。关键词：社会网络，信息传播，影响力最大化，期望II南京大学硕士学位论文THESIS：AbstractAStudyofExpectationbasedInfluenceMaximizationProbleminSocialNetworksSPECIALIZATION：ComputerSoftware&TheoryPOSTGRADUATE：ZHANGYaoⅣ匝NTOR：Prof．CHENDaoxu&Prof．GUQingAbstractWiththe

7、rapiddevelopmentofnewonlineapplicationssuchasFacebookandTwitter，thenumberofinformationcascadesontheIntemetincreasestremendously．Howtofindthemostinfluentialnodesinthemassivedataofnetworkshasbecomeahottopicintheareasofbothdataminingandsocialnetworksanalysis．I

8、nfluencemaximizationproblemisconsideredtotacklesuchissue，whichCanapplytoalargeamountoffieldsincludingvirusresearch，onlineapplicationpromotionandmarketinganalysisThisthesisproposesallexpectationbasedmet