基于社会网络影响力模型及其算法研究

《基于社会网络影响力模型及其算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多臻．》夕l硕士学位论文18l7269社会网络影响力模型及其算法研究ResearchonInfluenceModelsandAlgorithmsofSocialNetworks作者：黎雷导师：林友芳北京交通大学2010年7月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授

2、权说明)学位论文作者签名：辞驾导师签名：叮寸，双劣签字日期：扣f0年lr月20日签字日期：Zof口年6月≥D日中图分类号：TPl82；N941．4UDC：004．8学校代码：10004密级：公开北京交通大学硕士学位论文社会网络影响力模型及其算法研究ResearchonInfluenceModelsandAlgorithmsofSocialNetworks作者姓名：黎雷导师姓名：林友芳学位类别：工学学科专业：计算机科学与技术学号：08120519职称：副教授学位级别：硕士研究方向：数据与知识工程北京交通大学2010年7月致谢本论文的工

3、作是在我的导师林友芳副教授的悉心指导下完成的，林友芳副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来林友芳老师对我的关心和指导。实验室的魏名元老师和韩升老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和帮助，在此向魏名元老师和韩升老师表示衷心的谢意。武志吴博士和万怀宇博士对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在实验室工作及撰写论文期间，兰如钦等同学对我论文的研究工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢我的家人，他们的理解和支持给予我

4、充足的动力，使我能够在学校专心完成我的学业。摘要营销领域的“口碑效应’’现象和“病毒式营销"推广方式提出了如何在人群中寻找影响力最大的用户的问题。该问题与社会网络影响力模型及其算法领域的研究内容有着很高的契合度。影响力最大化问题被引入社会网络研究领域后，成为近年来学术界的一大研究热点。研究者根据现实网络中影响力传播规律，结合理论分析，建立了各种传播模型，并将影响力最大化问题转化为传播模型上的算法的问题。本文首先重点研究了独立级联模型和线性阈值模型这两种基本的影响力传播模型，定义了传播模型上影响力的传播机制。同时，本文还阐述了影响力最

5、大化问题的相关性质、研究思路和典型算法。通过总结和对比典型算法的特点，在分析其优点和不足的基础上，提出了将有向图的强连通分量分解思想应用于影响力最大化问题的新算法，并将该新算法与两种典型算法进行了性能对比和分析。分析结果显示，新算法的时间复杂度要低于两种典型算法。本文的研究以本实验室与中国移动通信研究院合作项目“用户行为分析系统"为实验平台，建立传播模型和传播机制，实现新算法以及典型算法，并使用摘取自斯坦福大学以及密歇根大学网站的多个真实社会网络数据集进行了一系列实验。实验结果表明，在影响力最大化问题的规模较大的情况下，与典型算法相

6、比，本文提出的新算法能够用更少的时间、更高的效率解决问题。这一结论与理论分析结果相符。关键词：影响力算法；强连通分量分解；影响力模型；社会网络；可视化分类号：TPl82；N941．4j匕立交适太堂亟±堂僮j金塞△垦墨!B△￡IABSTRACT”Word—of-mouth”and”viralmarketing”effectsinmarketinghaveraisedtheproblemofhowtofendtheinflu．entialmembersofpeople．Thisproblemhighlycorrespondstother

7、esearchoninfluencemodelsandalgorithmsofsocialnetworks．Themaximizationofinfluencehasbeenafocusinacademiainrecentyearssinceitwasintroducedinthefieldofsocialnetworkanalysis．Basingondisciplinesofinfluencepropagationinrealnetworkandcombiningwiththeoreticalanalysis，theresear

8、chersestablishvariouscommunicationmodelsandtranslatetheinfluencemaximizationproblemintoallalgorithmproblemofpropagati