基于标签传播方法的重叠社区检测算法研究

论文摘要

信息化的、智能化的时代悄然而至,复杂网络无疑是研究信息流动的重要途径。社区检测是网络科学研究中的一个重要分支,能够刻画网络的特征,分析网络的结构,对于认识网络的特质、预测网络更替规律、控制网络的发展趋势、指导网络中节点的决策等等。现存的文献以找到网络中的非重叠社区者居多,随着研究发现节点并非只属于唯一社区,使得重叠社区检测算法的研究逐步兴起。本文主要以标签传播思想为指导,通过完善标签传播算法来找到重叠社区。针对LPAs、SLPA算法的缺陷进行相应的改进。由于原网络一般结构不甚清晰,网络内部混沌复杂,寻找网络社区存在困难,所以本文提出一种基于LPA的线图转换算法E-LPA,通过提出的线图可以使原本具有社区结构的网络社区结构更为明显,创新地以标签传播的方式传播边的标签,完成边的社区划分,然后通过目标函数优化对标签传播后的粗糙社区进行修正,将误分社区合并,从而得到社区结构,而且该算法是可以检测重叠节点,使得LPA算法从检测非重叠社区向检测重叠社区过渡。针对SLPA算法的抖动性以及算法划分质量问题提出CSLPA算法,该算法通过寻找核心节点构造核心社区,以提出的贡献值指标对于未处理的节点进行归属处理形成初始社区,然后以SLPA算法对初始社区内节点的修正,得到划分后的社区结果。在人工数据集和真实数据集下进行实验,以扩展模块度和划分密度为评价指标,证明在社区划分质量方面E-LPA及CSLPA算法比八个经典对比算法在EQ指标下可提高10%-60%,而在PD指标下可提高20%-70%,且结果稳定,算法健壮性较好。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 论文的研究内容
•   1.4 论文的组织结构
• 第二章 理论基础及相关工作
•   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 谱分析算法
•     2.5.3 层次划分方法
•     2.5.4 基于目标函数优化
•     2.5.5 基于随机游走的重叠社区检测算法
•     2.5.6 标签传播算法
•   2.6 现有复杂网络重叠社区检测算法
•     2.6.1 基于完全图的检测算法
•     2.6.2 基于局部扩展优化的检测算法
•     2.6.3 基于节点分裂的重叠社区检测算法
•     2.6.4 基于标签传播的重叠社区检测算法
•   2.7 本章小结
• 第三章 基于边的标签传播的重叠社区检测算法
•   3.1 相关概念
•     3.1.1 节点自网络
•     3.1.2 节点密度
•     3.1.3 标签传播
•   3.2 算法描述
•     3.2.1 初始化
•     3.2.2 关联矩阵转化
•     3.2.3 边的标签传播
•     3.2.4 修正重叠节点
•   3.3 算法实例
•   3.4 复杂度分析
•   3.5 本章小结
• 第四章 基于节点贡献值的标签传播重叠社区检测算法
•   4.1 基本概念
•     4.1.1 核心社区
•     4.1.2 度中心性
•     4.1.3 聚类系数
•     4.1.4 贡献指标
•   4.2 算法概述
•     4.2.1 寻找核心社区结构
•     4.2.2 构建初始社区结构
•     4.2.3 标签传播阶段
•     4.2.4 后处理阶段
•   4.3 算法实例
•   4.4 算法时间复杂度
•   4.5 本章小结
• 第五章 实验与分析
•   5.1 实验数据集介绍
•     5.1.1 人工数据集
•     5.1.2 真实数据集
•   5.2 评价指标
•     5.2.1 模块度与扩展模块度
•     5.2.2 划分密度
•   5.3 实验结果分析与展示
•     5.3.1 E-LPA算法运行在人工数据集结果与分析
•     5.3.2 E-LPA算法运行在真实数据集结果与分析
•     5.3.3 CSLPA算法运行在真实数据集结果与分析
•   5.4 小结
• 第六章 总结与展望
•   6.1 论文工作总结
•   6.2 展望
• 参考文献
• 在学期间的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 闫君

导师: 徐玉生

关键词: 复杂网络,社区检测,标签传播,线图,贡献值

来源: 兰州大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州大学

分类号: O157.5

总页数: 69

文件大小: 4483K

下载量: 144