基于SLPA的重叠社区检测算法研究

论文摘要

随着人类社会步入网络信息时代,人们生产生活当中充溢着纷繁复杂的数据,而网络作为传播信息的重要载体,对其内部结构的研究逐步成为网络科学领域的一个重大研究议题,学术界称之为社区检测。发现复杂网络中社区结构对于研究网络的本质、功能及演变趋势具有重要的理论意义和实用价值。在传统的社区检测算法中,重叠社区检测算法较非重叠社区检测算法更符合真实的网络划分,故本文基于经典的标签传播算法SLPA提出两种改进的重叠社区检测算法。论文主要贡献如下:(1)DSLPA算法针对SLPA算法在标签更新阶段和标签传播阶段存在的随机性,前一阶段通过PageRank算法确定节点标签更新顺序,后一阶段结合改进Jaccard相似性指标在标签选取不唯一时进行二次决策,进而改进原算法中随机性带来的不确定性;(2)MSLPA算法将SLPA算法与模块度优化思想相结合,在算法初始阶段通过模块度比率最大化进行网络粗聚类,同时在标签传播阶段,利用资源分配指标RA实现标签选取,当结果不唯一时,采取出现频率最高选取法确定更新标签,使得社区检测结果更符合真实的网络结构。DSLPA算法和MSLPA算法在五组人工数据集和六组真实数据集中进行实验,通过标准化互信息NMI、扩展模块度EQ和划分密度PD等指标可知,两种算法均具有较为显著的优势,同时算法收敛较快,结果稳定,以此验证本文提出的算法具有较好的实施性和健壮性。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 论文研究内容
•   1.4 论文组织结构
• 第二章 理论基础与相关工作
•   2.1 复杂网络概述
•   2.2 社区基本概念
•   2.3 节点重要性与相似性
•     2.3.1 节点重要性指标
•     2.3.2 节点相似性指标
•   2.4 传统社区检测算法
•     2.4.1 基于图分割的方法
•     2.4.2 基于谱分析的方法
•     2.4.3 基于图动力学的方法
•     2.4.4 基于层次划分的方法
•     2.4.5 基于信息传播的方法
•     2.4.6 基于模块度优化的方法
•   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.7 本章小结
• 第三章 通过提高SLPA确定性寻找重叠社区
•   3.1 相关概念
•     3.1.1 节点重要性
•     3.1.2 节点相似性
•     3.1.3 标签传播
•     3.1.4 重叠节点判定
•   3.2 算法思想
•   3.3 算法步骤
•     3.3.1 初始化
•     3.3.2 标签传播
•     3.3.3 后处理输出
•     3.3.4 算法流程图
•   3.4 算法实例
•   3.5 时间复杂度分析
•   3.6 本章小结
• 第四章 基于模块度优化的改进SLPA算法
•   4.1 相关概念
•     4.1.1 模块度
•     4.1.2 标签传播
•     4.1.3 重叠节点判定
•   4.2 算法思想
•   4.3 算法步骤
•     4.3.1 参数初始化
•     4.3.2 模块度预处理
•     4.3.3 标签传播
•     4.3.4 后处理输出
•     4.3.5 算法流程图
•   4.4 算法实例
•   4.5 时间复杂度分析
•   4.6 本章小结
• 第五章 实验论证与分析
•   5.1 评价指标
•     5.1.1 标准化互信息
•     5.1.2 扩展模块度
•     5.1.3 划分密度
•   5.2 实验数据集说明
•     5.2.1 人工网络数据集
•     5.2.2 真实网络数据集
•   5.3 结果分析与展示
•     5.3.1 DSLPA在人工数据集的结果分析
•     5.3.2 DSLPA在真实数据集的结果分析
•     5.3.3 MSLPA在人工数据集的结果分析
•     5.3.4 MSLPA在真实数据集的结果分析
•   5.4 本章小结
• 第六章 总结与展望
•   6.1 论文总结
•   6.2 工作展望
• 参考文献
• 在学期间的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 张静宜

导师: 马志新

关键词: 社区检测,重叠社区,标签传播,模块度,节点相似性

来源: 兰州大学

年度: 2019

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

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

单位: 兰州大学

分类号: TP301.6;O157.5

总页数: 75

文件大小: 8181K

下载量: 78