复杂网络中的社区发现算法研究

发布时间：2017-05-23 15:20

  本文关键词：复杂网络中的社区发现算法研究，由笔耕文化传播整理发布。

【摘要】：随着复杂网络研究的兴起,从复杂网络的角度研究复杂系统受到了越来越多的关注。现实世界中大量的复杂系统均可以用复杂网络来描述。社区结构作为复杂网络的重要特性之一,引起了研究者的广泛关注。社区发现即为挖掘复杂网络中的模块化的社区结构的过程,这对于理解复杂网络的功能、发现复杂网络中隐藏的规律和预测复杂网络的行为具有重要的意义。然而,随着网络规模不断扩大,网络结构更加复杂,社区发现也变得异常困难。目前,已有的社区发现算法还存在以下问题:(1)现有的社区发现算法难以准确地发现稳定的重叠社区结构;(2)基于节点的社区发现算法难以发现网络中重叠度较高的社区结构;(3)传统的社区发现算法仅仅关注网络中的模块化社区结构,无法进一步识别社区中的层次关系。本文针对上述问题展开研究,主要工作和研究成果如下:1.提出了一种基于非重叠极大子团的标签传播社区发现算法。该算法在标签传播算法的基础上,对其进行三个方面的改进:在标签初始化阶段,通过查找网络中非重叠的极大子团结构,赋予每个非重叠的极大子团唯一的标签;在标签传播阶段,通过选取具有最大标签传播率的标签来更新节点标签;在社区调整阶段,通过合并相似度较高的社区来提升社区发现的质量。将该算法分别应用于计算机生成网络和真实的社会网络,实验结果表明:该算法很好地解决了标签传播算法的鲁棒性问题,并能准确地发现网络中的重叠社区。2.提出了一种基于核心链路的重叠社区发现算法。相较于当前的基于节点的重叠社区发现算法,该算法从链路的角度出发,通过选取核心链路,并根据链路影响力的强弱不断吸引外层链路进而形成链路社区结构;再将链路社区转化为节点社区,经过节点社区调整后,得到全局最优的重叠社区结构。该算法是一种无监督算法,无需输入额外参数。将该算法分别应用于计算机生成网络和真实的社会网络,实验结果表明,相较于其它算法,该算法能够更好地发现重叠度较高的社区结构。3.提出了一种基于种子节点集的社区层次结构发现算法。该算法通过选取种子节点,并根据余弦相似度的大小添加其最近邻节点共同构成种子节点集;再由种子节点集出发,基于分辨率公式进行社区层次结构探测,根据节点加入社区的度值比来判断是否到达层次边界;最后在已发现完毕的社区外选取新的种子节点集,并由此出发直到全网络的社区层次结构发现完毕。将该算法分别应用于人工网络和真实社会网络,实验表明,相较于其它算法,该算法能够准确地发现网络中全部的社区层次结构。
【关键词】：复杂网络 社区发现 重叠社区 层次社区 标签传播 链路聚类 社区分辨率
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• ABSTRACT5-11
• 第一章 绪论11-21
• 1.1 课题研究背景11-13
• 1.2 课题研究意义13-14
• 1.3 国内外研究现状14-16
• 1.4 问题提出16-17
• 1.4.1 现有的社区发现算法难以准确地发现稳定的重叠社区结构16-17
• 1.4.2 基于节点的社区发现算法难以发现网络中重叠度较高的社区结构17
• 1.4.3 传统的社区发现算法无法进一步识别社区中的层次关系17
• 1.5 本文主要内容和组织结构17-21
• 1.5.1 主要内容17-19
• 1.5.2 组织结构19-21
• 第二章 基于非重叠极大子团的标签传播社区发现算法21-33
• 2.1 引言21
• 2.2 LPA算法21-22
• 2.3 LPAc算法22-26
• 2.3.1 非重叠极大子团提取22-23
• 2.3.2 标签传播率概率模型提出23-24
• 2.3.3 社区结构调整24-25
• 2.3.4 算法描述25
• 2.3.5 算法复杂度分析25-26
• 2.4 实验结果及分析26-31
• 2.4.1 评价指标26-27
• 2.4.2 计算机生成网络27-30
• 2.4.3 真实社会网络30-31
• 2.5 本章小结31-33
• 第三章 基于核心链路的重叠社区发现算法33-41
• 3.1 引言33
• 3.2 CLCD算法33-36
• 3.2.1 基本思想33-34
• 3.2.2 基本概念34
• 3.2.3 算法描述34-36
• 3.2.4 算法复杂度分析36
• 3.3 实验结果及分析36-39
• 3.3.1 评价指标37
• 3.3.2 计算机生成网络37-39
• 3.3.3 真实社会网络39
• 3.4 本章小结39-41
• 第四章 基于种子节点集的社区层次结构发现算法41-49
• 4.1 引言41-42
• 4.2 HSS算法42-44
• 4.2.1 算法准备42-43
• 4.2.2 算法描述43
• 4.2.3 算法复杂度分析43-44
• 4.3 实验结果及分析44-47
• 4.3.1 计算机生成网络44-45
• 4.3.2 真实社会网络45-47
• 4.4 本章小结47-49
• 第五章 总结与展望49-51
• 5.1 全文总结49
• 5.2 本文的主要创新点49
• 5.3 下一步研究工作展望49-51
• 致谢51-53
• 参考文献53-57
• 作者简历 攻读硕士学位期间完成的主要工作57

【参考文献】

中国期刊全文数据库 前7条

1 张泽华;苗夺谦;钱进;;邻域粗糙化的启发式重叠社区扩张方法[J];计算机学报;2013年10期

2 易秀双;韩业挺;王兴伟;;一种基于节点影响力的局部社区发现算法[J];小型微型计算机系统;2013年09期

3 潘磊;金杰;王崇骏;谢俊元;;社会网络中基于局部信息的边社区挖掘[J];电子学报;2012年11期

4 骆志刚;丁凡;蒋晓舟;石金龙;;复杂网络社团发现算法研究新进展[J];国防科技大学学报;2011年01期

5 黄健斌;孙鹤立;Dustin BORTNER;刘亚光;;从链接密度遍历序列中挖掘网络社团的层次结构[J];软件学报;2011年05期

6 李晓佳;张鹏;狄增如;樊瑛;;复杂网络中的社团结构[J];复杂系统与复杂性科学;2008年03期

7 解(亻刍);汪小帆;;复杂网络中的社团结构分析算法研究综述[J];复杂系统与复杂性科学;2005年03期

  本文关键词：复杂网络中的社区发现算法研究，由笔耕文化传播整理发布。

，

本文编号：388341