复杂网络节点重要性排序与影响最大化研究

论文摘要

随着互联网技术的飞速发展,复杂网络逐渐成为人们获取信息的重要媒介。近年来复杂网络的分析研究深受广大学者的青睐。其中节点重要性排序、影响最大化问题有着重要的现实意义,下面将针对这两个问题进行论述。首先,针对K-shell算法划分粒度过大的问题,给出了一个新的指标来替换原始的Ks值,将同一层上节点影响力进一步区分。考虑到节点信息把控能力对其重要性的影响,给出了基于结构洞理论的节点信息把控能力度量指标。最后利用上面给出的两个指标,结合节点局部传播能力,提出一个新的节点重要性排序算法。该算法可以从节点的全局位置、局部传播能力和信息把控能力三个方面综合评价节点的重要程度。其次,针对贪心算法效率低的问题,给出了影响力局部更新机制,并结合网络的社区结构特征,提出融合社区结构和贪心思想的影响最大化算法。该算法分两阶段进行种子节点选取,第一阶段是启发选择阶段,先对网络进行社区划分,以社区为单位,用前面提出的节点重要性排序算法对社区内的节点进行排名,得到候选节点集和第一部分种子节点。第二阶段是贪心选择阶段,利用影响力局部更新机制在候选节点集中选择剩余种子节点。将两部分种子节点结合形成最终种子节点集。最后,在SIR模型和独立级联模型上分别对提出的两种算法使用不同的评价标准,与其他算法进行仿真对比实验。实验结果表明提出的节点重要性排序算法的排序结果优于其他算法,融合社区结构和贪心思想的影响最大化算法所选取的种子集可以使得信息传播的更快、更广。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 课题背景和意义
•   1.2 国内外研究现状
•     1.2.1 节点重要性排序问题的研究现状
•     1.2.2 影响最大化问题的研究现状
•   1.3 主要研究内容
•   1.4 本文组织结构
• 第2章 相关理论知识
•   2.1 复杂网络
•     2.1.1 复杂网络以及图的相关概念
•     2.1.2 复杂网络特性
•   2.2 节点重要度量性指标
•     2.2.1 基于近邻的排序方法
•     2.2.2 基于路径的排序方法
•     2.2.3 基于特征向量的排序方法
•   2.3 常用影响最大化算法
•     2.3.1 贪心类算法
•     2.3.2 启发式算法
•   2.4 社区划分算法
•   2.5 网络传播模型
•     2.5.1 独立级联模型
•     2.5.2 SIR模型
•     2.5.3 线性阈值模型
•   2.6 本章小结
• 第3章 基于NKS和 SHIC的节点重要性排序算法
•   3.1 引言
•   3.2 相关概念
•     3.2.1 符号定义
•     3.2.2 NKS分解的提出
•     3.2.3 网络的结构洞特征
•   3.3 基于NKS和 SHIC的节点重要性排序算法
•     3.3.1 相关定义以及算法思想
•     3.3.2 算法设计
•   3.4 本章小结
• 第4章 融合社区结构和贪心思想的影响最大化算法
•   4.1 引言
•   4.2 相关概念
•     4.2.1 符号定义
•     4.2.2 网络的社区结构特性
•   4.3 融合社区结构和贪心思想的影响最大化算法
•     4.3.1 相关定义以及算法思想
•     4.3.2 算法设计
•   4.4 本章小结
• 第5章 实验结果和分析
•   5.1 实验环境
•   5.2 实验仿真模型和评价标准
•     5.2.1 节点重要性的排序算法评价标准
•     5.2.2 影响最大化算法评价标准
•   5.3 节点重要性排序算法NKSIC的实现与结果分析
•     5.3.1 实验数据集
•     5.3.2 节点重要性排序算法实验结果分析
•   5.4 影响最大化算法CGIM的实现与结果分析
•     5.4.1 实验数据集
•     5.4.2 影响最大化算法实验结果分析
•   5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢

文章来源

类型: 硕士论文

作者: 周学文

导师: 刘永山,张淑杰

关键词: 影响最大化,节点重要性,算法,结构洞,贪心算法

来源: 燕山大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 燕山大学

分类号: TP301.6;O157.5

DOI: 10.27440/d.cnki.gysdu.2019.000463

总页数: 60

文件大小: 1616K

下载量: 88