基于社区结构和阈值的影响力最大化算法研究

论文摘要

随着互联网的快速发展,具有社交属性的应用越来越多,例如最右,趣头条等。这些应用的特点是用户量庞大、用户之间相互关联、信息在这些应用上传播速度快,范围广。研究病毒式营销,舆情分析和流量监控等影响力最大化问题是非常重要的。但是,现有解决影响力最大化问题的启发式算法没有考虑到种子节点影响力重叠的问题。针对影响力最大化问题中种子节点存在影响力重叠的问题展开研究。首先,由于网络的社区结构会影响信息的传播范围,提出了基于社区结构的影响力最大化算法CIMA。该算法定义了社区适应度和节点贡献度来删除社区中连边稀疏的节点和选择与社区联系紧密的节点,并以此为基础划分社区;基于社区划分的结果,在各个社区中选择度最大的节点作为种子节点。其次,针对影响力最大化问题的时间复杂度较高的问题,提出了基于覆盖阈值的影响力最大化算法CTMD。该算法根据改进的影响力估计算法k-shell来计算网络中所有节点的影响力,选择影响力最大的节点作为第一个种子节点;计算种子节点集合两级邻居以内的节点被激活的概率;基于覆盖阈值θ,把易激活的节点标记为覆盖状态,选择影响力最大并且处于非覆盖状态的节点作为种子节点。最后,在人工网络和真实的网络数据集上对所提出的算法进行了实验验证。对CIMA算法、度最大算法Degree和影响力排名影响力估计算法IRIE的影响效果进行了比较与分析;在独立级联IC和权重级联WC模型中,对CTMD算法、核覆盖算法CCA、Degree算法和IRIE算法的影响效果和运行时间进行比较与分析。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 课题研究背景及意义
•     1.1.1 研究背景
•     1.1.2 研究意义
•   1.2 国内外研究现状
•   1.3 本文的研究内容
•   1.4 本文的组织结构
• 第2章 相关工作
•   2.1 社交网络的结构特征
•   2.2 常见传播模型
•     2.2.1 独立级联模型
•     2.2.2 线性阈值模型
•   2.3 常见算法
•     2.3.1 Greedy算法
•     2.3.2 MIA算法
•     2.3.3 IRIE算法
•   2.4 本章小结
• 第3章 基于社区结构的影响力最大化算法
•   3.1 引言
•   3.2 CIMA算法的非重叠社区发现
•     3.2.1 小社区发现
•     3.2.2 小社区发现实例说明
•     3.2.3 小社区合并
•     3.2.4 社区整合
•   3.3 CIMA算法的种子节点选择策略
•     3.3.1 种子节点选择方法
•     3.3.2 CIMA算法步骤
•     3.3.3 CIMA算法描述
•   3.4 实验与结果分析
•     3.4.1 验证CIMA算法社区划分的有效性
•     3.4.2 验证CIMA算法的有效性
•   3.5 本章小结
• 第4章 基于覆盖阈值的影响力最大化算法
•   4.1 引言
•   4.2 k-shell算法和CCA算法介绍
•     4.2.1 k-shell算法描述
•     4.2.2 k-shell算法的不足
•     4.2.3 CCA算法描述
•     4.2.4 CCA算法的不足
•   4.3 基于覆盖阈值的影响力最大化算法
•     4.3.1 基于ks值和传播概率的影响力估计
•     4.3.2 CTMD算法的覆盖策略与说明
•     4.3.3 CTMD算法描述
•     4.3.4 实例说明
•     4.3.5 算法伪代码
•     4.3.6 算法复杂度分析
•   4.4 实验结果分析
•     4.4.1 实验数据集
•     4.4.2 IC模型下的实验结果与分析
•     4.4.3 WC模型下的实验结果与分析
•     4.4.4 提高CTMD算法的影响效果
•     4.4.5 运行时间
•   4.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢

文章来源

类型: 硕士论文

作者: 刘贤

导师: 陈晶

关键词: 社交网络,社区结构,节点影响力,影响力最大化,覆盖阈值

来源: 燕山大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 燕山大学

分类号: O224

DOI: 10.27440/d.cnki.gysdu.2019.001165

总页数: 64

文件大小: 2226K

下载量: 26