基于连接模式的相关分析及带偏置的随机游走的社团检测方法研究

论文摘要

复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的这些模块,有助于深层探究复杂网络内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,社团检测受到很多研究者的广泛关注,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,本文通过顶点的连接模式之间的相关性分析以及模拟带偏置的随机游走过程,提出了两种社团检测算法:（1）基于连接模式的相关分析的社团检测算法。该算法首先获得顶点间的连接模式,计算相关系数得到连接模式间的相关性,获得must-link与cannot-link成对约束,并根据must-link关系的传递性,对must-link及cannot-link关系集合进行扩展。然后将扩展后的cannot-link集合作为种子节点,结合must-link关系构造社团结构的框架。最后用最小生成树方法,将其余节点划分到相应社团,得到最终的社团结构。（2）基于带偏置的信号传播机制的随机游走算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑信号的衰减,为每条边增加了衰减因子,对信号传播过程进行限定。通过模拟信号的传播,将网络每个顶点均作为信号源重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证本文所提出方法的性能,本文在多个实际网络数据集以及人工合成网络数据集上进行了实验,并与相关算法的检测结果进行对比检测,实验结果表明,本文提出的算法能够从网络中提取出高质量的社团结构。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 本文主要研究内容
•   1.3 本文的组织结构
• 第二章 社团检测相关理论基础与研究现状
•   2.1 相关符号定义
•   2.2 连接模式的相关概述
•   2.3 常见的社团检测算法
•     2.3.1 图论方法
•     2.3.2 模块度优化算法
•     2.3.3 层次算法
•     2.3.4 标签传播算法及其变体
•     2.3.5 随机游走算法
•   2.4 社团结构质量评价指标
•     2.4.1 模块度（Modularity）
•     2.4.2 归一化互信息量（NMI）
•   2.5 实验环境及实验数据
•     2.5.1 实验环境
•     2.5.2 实验数据
• 第三章 基于连接模式的相关分析的社团检测算法CCP
•   3.1 CCP算法的思想
•   3.2 CCP算法具体描述
•   3.3 时间复杂度分析
•   3.4 实验
•     3.4.1 参数设置
•     3.4.2 CCP算法在实际数据集上的实验结果及分析
•     3.4.3 CCP算法在合成网络上的实验结果及分析
•     3.4.4 小结
• 第四章 基于带偏置的信号传播机制的随机游走算法CRSB
•   4.1 相关理论
•     4.1.1 随机游走
•     4.1.2 k-Means算法
•   4.2 CRSB算法详细介绍
•   4.3 算法时间复杂度分析
•   4.4 实验
•     4.4.1 参数设置
•     4.4.2 CRSB算法在实际数据集上的实验结果及分析
•     4.4.3 CRSB算法在合成网络上的实验结果及分析
•     4.4.4 小结
• 第五章 总结与展望
•   5.1 工作总结
•   5.2 展望
• 参考文献
• 在学期间的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 尹欣红

导师: 陈晓云

关键词: 社团检测,连接模式,成对约束,随机游走,信号传播

来源: 兰州大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州大学

分类号: O157.5

总页数: 58

文件大小: 4659K

下载量: 41