基于扩展独立级联模型的竞争影响最大化传播

发布时间：2017-08-17 08:21

  本文关键词：基于扩展独立级联模型的竞争影响最大化传播

  更多相关文章： 社会网络 子模性 竞争影响最大化 扩展独立级联模型 CELF算法

【摘要】：近年来,随着移动通信和web技术的不断发展,越来越多的人开始使用社交网络,比如：Facebook、 Twitter、 Linkedin、人人网和新浪微博等,进行在线交流和传播信息。这吸引了大批的科研工作者对社会网络的关注和研究,他们研究在线社会网络的空间结构,信息传播特性,博文内容分析,以及社会网络中的推荐系统等。 本论文主要研究存在实体(产品或者观点)相互竞争的情况下,如何使某种实体影响传播最大化的问题。其中,社会网络影响最大化是指给定种子结点的个数k和某一种传播模型,找出k个最具有影响力的结点集。Kemple等人[1]提出两种经典的信息传播模型：线性阈值模型(Linear Threshold Model, LTM)和独立级联模型(Independent Case Model，， ICM)。线性阈值模型适合于描述个体的行为受多个个体的影响,而独立级联模型适合于描述个体的行为只受一个个体的影响,但是,这两种传播模型只适用于一种实体在社会网络中传播的情形。在现实生活中,存在两种或两种以上实体竞争传播的情形,为了研究这种竞争影响传播,本文从以下几个方面开展工作： (1)扩展了经典独立级联模型,使其包含两种及两种以上的竞争影响传播。 (2)主要解决在扩展独立级联模型下,给出一种实体(产品或者观点)的种子结点集合,如何找出另一种实体最有影响力的k个种子结点集。 (3)证明了基于扩展独立级联模型的竞争影响传播目标函数具有单调性(monotonicity)和子模性(submodularity),因此使用贪心算法或者cost effective lazy forward——CELF方法可以得到最优解的1-1/e。 (4)实现了本文算法,并进行了初步的实验,验证了本文所提方法的可行性及有效性。
【关键词】：社会网络 子模性 竞争影响最大化 扩展独立级联模型 CELF算法
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;TP393.09
【目录】：

• 摘要3-4
• Abstract4-7
• 第1章 绪论7-13
• 1.1 研究背景和意义7-9
• 1.1.1 研究背景7-8
• 1.1.2 研究意义和目的8-9
• 1.2 国内外研究现状9-10
• 1.3 本文主要研究内容10-11
• 1.4 本文组织结构11-13
• 第2章 背景知识和研究基础13-23
• 2.1 社会网络13-15
• 2.1.1 社会网络的来源和定义13-14
• 2.1.2 社会网络的特点14-15
• 2.2 影响最大化15-17
• 2.3 传播模型介绍17-23
• 2.3.1 线性阈值模型17-19
• 2.3.2 独立级联模型19-23
• 第3章 竞争影响传播模型23-29
• 3.1 问题描述23
• 3.2 可能图中“活边”的选取23-24
• 3.3 扩展独立级联模型24-29
• 第4章 竞争影响传播最大化29-37
• 4.1 竞争影响传播最大化的目标函数29
• 4.2 目标函数的单调性和子模性29-32
• 4.3 竞争影响最大化的近似算法32-37
• 4.3.1 算法思想介绍32-34
• 4.3.2 具体算法34-37
• 第5章 实验结果37-43
• 5.1 实验相关介绍37-39
• 5.2 实验设置39
• 5.3 实验结果分析39-43
• 第6章 总结与展望43-45
• 6.1 论文总结43
• 6.2 未来工作展望43-45
• 附录45-55
• A1.硕士期间参与的科研成果45
• A2.论文中主要算法的实现代码45-55
• 参考文献55-59
• 致谢59

【参考文献】

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

1 樊鹏翼;王晖;姜志宏;李沛;;微博网络测量研究[J];计算机研究与发展;2012年04期

2 田家堂;王轶彤;冯小军;;一种新型的社会网络影响最大化算法[J];计算机学报;2011年10期

3 王晟;王子琪;张铭;;个性化微博推荐算法[J];计算机科学与探索;2012年10期

4 徐恪;张赛;陈昊;李海涛;;在线社会网络的测量与分析[J];计算机学报;2014年01期

5 吴信东;李毅;李磊;;在线社交网络影响力分析[J];计算机学报;2014年04期

本文编号：687988