基于线图谱分析的复杂网络重叠社团发现算法研究

发布时间：2017-10-04 23:05

  本文关键词：基于线图谱分析的复杂网络重叠社团发现算法研究

  更多相关文章： 复杂网络 重叠社团发现 线图 谱分析 层次聚类

【摘要】：网络的社团结构(Community Structure)作为复杂网络的一个重要特征,发现网络的社团结构是一项非常基础且重要的工作。实际中社团的重叠性(Overlapping)和社团的层次性(Hierarchical Structure)交织在一起,二者的关系十分紧密,单纯忽略其中的任何一方来研究另一方,其结果都不能准确的描述网络中的社团结构。社团发现算法的研究已经得到了学术界的广泛关注,但是对重叠社团发现算法,尤其是利用边社团进行重叠社团发现算法的研究还是比较新的研究领域,具有很广阔的研究前景和重要的现实意义。本文通过对谱分析方法的研究,首次将该方法应用在边社团发现算法上,实现了利用谱分析进行边社团发现。一方面将谱分析方法改进为能够发现重叠社团的算法,另一方面,谱分析方法提供了一种新颖的定量边与边相似度的方式。在基于一维非平凡特征向量的重叠社团发现中,本文分别进行了基于线图标准化拉普拉斯矩阵和基于线图归一化拉普拉斯矩阵一维非平凡特征向量的社团发现；在基于二维非平凡特征向量的重叠社团发现中,本文利用基于线图标准化拉普拉斯矩阵的二维非平凡特征向量空间,进行了兼顾社团层次性和重叠性的复杂网络重叠社团发现算法的研究。在空手道俱乐部网络(Zachary Karate Club)和海豚社交网络(Dolphin social network)与Ahn在2010年提出的算法进行了比较分析。实验结果表明,本文算法能实现复杂网络重叠社区发现,与Ahn的算法相比具有更好的性能。
【关键词】：复杂网络 重叠社团发现 线图 谱分析 层次聚类
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要3-4
• Abstract4-7
• 第一章 绪论7-13
• 1.1 研究背景及意义7-9
• 1.2 国内外研究现状9-11
• 1.2.1 非重叠社团发现算法9-10
• 1.2.2 重叠社团发现算法10-11
• 1.3 本文主要工作11
• 1.4 论文组织机构11-13
• 第二章 相关理论与方法简介13-22
• 2.1 图及图的矩阵描述13-16
• 2.1.1 邻接矩阵(Adjacency Matrix)13
• 2.1.2 关联矩阵(Incidence matrix)13-14
• 2.1.3 拉普拉斯矩阵(Laplacian matrix)14-15
• 2.1.4 线图及其邻接矩阵15-16
• 2.2 谱分析方法16-18
• 2.2.1 基于标准化拉普拉斯矩阵的谱分析16-17
• 2.2.2 基于归一化拉普拉斯矩阵的谱分析17-18
• 2.3 基于边社团的重叠社团发现算法18-21
• 2.4 本章小结21-22
• 第三章 基于一维非平凡特征向量空间的重叠社团发现22-46
• 3.1 线图标准化拉普拉斯矩阵的谱二分法22-33
• 3.1.1 谱二分法基本原理22
• 3.1.2 线图的标准化拉普拉斯矩阵22-23
• 3.1.3 算法步骤与实现23-24
• 3.1.4 实验结果分析24-33
• 3.1.5 小结33
• 3.2 线图归一化拉普拉斯矩阵的谱分析33-45
• 3.2.1 算法步骤与实现33-34
• 3.2.2 实验结果分析34-44
• 3.2.3 小结44-45
• 3.3 本章小结45-46
• 第四章 基于二维非平凡特征向量空间的重叠社团发现46-69
• 4.1 算法原理46-47
• 4.2 拉普拉斯矩阵特征向量选择47-48
• 4.3 特征向量空间中相似性度量标准的选择48-54
• 4.3.1 相似性度量标准48-49
• 4.3.2 相似性度量比较的标准49-51
• 4.3.3 相似性度量的比较实验及结果分析51-54
• 4.4 算法实现与实验结果分析54-68
• 4.4.1 空手道俱乐部网络54-59
• 4.4.2 海豚社交网络59-68
• 4.5 本章小结68-69
• 第五章 总结与展望69-70
• 5.1 工作总结69
• 5.2 未来工作的展望69-70
• 参考文献70-72
• 在学期间的研究成果72-73
• 致谢73

【参考文献】

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

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

中国博士学位论文全文数据库 前2条

1 徐峰;互联网宏观拓扑结构中社团特征演化分析及应用[D];东北大学;2009年

2 武志昊;复杂网络中的重叠社团发现问题研究[D];北京交通大学;2013年

，

本文编号：973346