社会网络中影响力最大化问题的算法设计与分析

发布时间：2017-04-16 23:12

  本文关键词：社会网络中影响力最大化问题的算法设计与分析，由笔耕文化传播整理发布。

【摘要】：近年来,随着电子设备的不断普及以及社交领域的不断发展,人与人之间的交流联系变得越来越密切方便,消息在人们之间的传递也愈加的方便快捷。如何利用人们之间形成的关系网络来进行信息的传播,逐渐得到了研究者们的关注。受到营销领域中“口碑效应”和“病毒式营销”策略的影响,逐步演化出了影响力最大化问题(简称为IMP问题)。影响力最大化问题要求研究者根据网络的结构特征,结合信息的传播特性,建立信息的传播模型,设计有效的算法,使得最终影响力在网络中能够最大限度的进行传播。影响力最大化问题要求我们从网络中选取若干节点,使得以他们为初始节点来进行信息传播时,在网络中产生的影响力能够达到最大。其研究不仅具有理论意义,而且还具有广泛的应用前景。社会网络上的影响力最大化问题研究对于广告发布、市场营销、消息传递以及科研合作等多个方面都有着十分重要的意义。本文首先介绍了社会网络中影响力最大化问题的来源以及国内外的研究现状,其次对用到的相关理论知识作了简单介绍,并且对研究中用到的两种基本传播模型进行了重点的研究。随后,对传统的启发式算法和贪心算法进行了分析和对比,针对网络的结构特征和信息的传播特性,考虑到现实网络中信息对时间的敏感性以及节点之间影响力的间接传递性,引入了影响因子。使用半定规划(SDP)方法设计了影响力最大化近似算法,同时提出了基于最大影响因子(MIF)的启发式算法和贪心策略。最后通过现实中的社会网络数据集进行了实验,分别从传播效果和传递效率两个方面对实验结果进行了分析,并且将MIF算法与基于最大顶点度(High-Degree)、基于距离(Distance)等传统的启发式算法和贪心算法进行了对比。实验结果表明,MIF算法与常见的启发式算法相比,其最终的传播效果要更好,传播效果与贪心算法接近；相比于贪心算法来讲,MIF算法与贪心算法传播效果接近,但是却大幅度的降低了运算时间,传递效率要好很多。同时,我们使用Gephi工具作了可视化表示,从而可以更加直观的观察到网络中节点的激活情况。
【关键词】：影响力最大化 社会网络 传播模型 近似算法 启发式算法
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.09
【目录】：

• 摘要8-9
• ABSTRACT9-11
• 第一章 绪论11-16
• 1.1 研究背景11-12
• 1.2 研究意义12
• 1.3 国内外研究现状12-14
• 1.4 本文的主要工作内容14-15
• 1.5 论文的组织结构15-16
• 第二章 理论基础16-23
• 2.1 社会网络16-18
• 2.1.1 社会网络的定义16
• 2.1.2 社会网络的性质16-17
• 2.1.3 基本概念17-18
• 2.1.4 影响力最大化问题定义18
• 2.2 次模函数的定义及性质18-19
• 2.3 影响力传播模型19-23
• 2.3.1 独立级联模型19-20
• 2.3.2 线性阈值模型20-23
• 第三章 影响力最大化算法23-38
• 3.1 启发式算法23
• 3.2 贪心近似算法23-27
• 3.2.1 定义23-24
• 3.2.2 算法描述24-25
• 3.2.3 相关定理25-26
• 3.2.4 改进的贪心算法26-27
• 3.3 基于SDP的近似算法27-34
• 3.3.1 影响因子28
• 3.3.2 影响力传递性28-30
• 3.3.3 半正定矩阵的定义及性质30
• 3.3.4 半定规划30-32
• 3.3.5 SDP算法表述32-34
• 3.4 MIF算法34-38
• 3.4.1 基于MIF的启发式算法34-35
• 3.4.2 基于MIF的贪心策略35-38
• 第四章 实验结果与分析38-48
• 4.1 实验数据38-39
• 4.2 实验方法39
• 4.3 实验过程39-40
• 4.3.1 模块设计39-40
• 4.3.2 传播模型简介40
• 4.4 实验结果分析40-45
• 4.5 可视化表示45-48
• 第五章 总结与展望48-50
• 5.1 总结48
• 5.2 展望48-50
• 参考文献50-54
• 致谢54-55
• 附录 攻读硕士学位期间发表的论文55-56
• 附件56

【共引文献】

中国期刊全文数据库 前3条

1 丘晓平;黄小兵;;网络化社会媒体的传播及应用[J];现代计算机;2013年30期

2 李永成;黄曙光;唐晋韬;刘金红;;有向在线社交网络中信息传播监测节点的选择[J];小型微型计算机系统;2014年02期

3 刘热;;移动社会网络中基于投票的影响力节点发现[J];西安文理学院学报(自然科学版);2014年03期

中国硕士学位论文全文数据库 前10条

1 叶鹏;基于集合覆盖贪心算法的二次覆盖算法[D];华南理工大学;2012年

2 韦吉洁;基于信任网络的病毒营销模型研究[D];哈尔滨工程大学;2012年

3 葛欣;面向主题的影响力最大化问题研究[D];云南大学;2013年

4 吴凯;基于微博的信息传播建模与节点影响力研究[D];解放军信息工程大学;2013年

5 许斌;中文微博的情感分析和影响力技术研究[D];解放军信息工程大学;2013年

6 郭进时;社会网络社区发现与影响力分析技术研究[D];解放军信息工程大学;2013年

7 于淼;微博消息影响力评估及最大化算法研究[D];哈尔滨工程大学;2013年

8 张鑫龙;基于协同过滤的传感器感知数据补全技术研究[D];东北大学;2013年

9 贺幸;微博影响力传播模型的改进与验证[D];中国科学技术大学;2014年

10 周生福;线性阈值模型下影响最大化算法研究[D];云南大学;2014年

  本文关键词：社会网络中影响力最大化问题的算法设计与分析，由笔耕文化传播整理发布。

，

本文编号：311891