复杂网络的社团划分算法研究

发布时间：2017-04-15 17:08

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

【摘要】：对于任何包含大量个体单元的复杂系统来说,我们都可以将其看作复杂网络来研究,复杂网络具有小世界、无标度和社团结构等诸多特征。社团结构主要刻画了网络中节点之间的相互关系,社团结构具有处于社团内部的节点联系较为紧密,处于社团之间的节点联系较为稀疏的显著特点,深入了解复杂网络中的社团结构有助于发现网络中潜藏着的规律和预测网络的行为。本文依据优化、启发式和相似度等不同的策略对常用社团划分算法进行了分类,并对其中的典型代表算法进行了详细的研究分析。针对相似度算法中存在的问题,本文提出了基于相似度的三元社团合并算法(Ternary Community Merging Algorithm based on Similarity,STCMA)。然后,本文将三元社团的概念应用于传统标签传播算法(Label Propagation Algorithm,LPA),进一步提出了基于三元社团的LPA算法(Label Propagation Algorithm based on Ternary Community,TCLPA)。(1)基于相似度的三元社团合并算法为解决在使用相似度判别哪些节点应该被放入同一个社团时可能出现的冲突问题,该算法构建了三元社团,并将三元社团作为网络中社团合并的基本元素。该算法通过引入三元社团,有效地增强了社团内部节点之间连接的紧密程度,更加清晰的凸显了网络中的社团结构。该算法的时间复杂度为??2O tm n,其中n代表网络中的节点数目,m代表连边数目,t代表节点相似度阈值更新的次数,该算法的提出能够较好的均衡时间复杂度与正确划分率两者之间的关系。(2)基于三元社团的LPA算法针对传统LPA算法中存在的两大不确定问题,一是在对网络中节点的标签信息进行更改时其节点更新顺序的不确定问题;二是在邻居节点集合中具有节点数目最多的标签信息类型不惟一时从中选取标签信息的不确定问题,该算法在三元社团的基础上构建了网络的初始核心社团,然后结合局部最优规则和深度计算规则计算网络中其他节点的标签依赖度,并据此对这些节点的标签信息做相应标记。本文分别采用人工合成网络与真实世界网络对提出的两种算法进行实验验证,通过标准化互信息、正确划分率和模块度等指标对实验结果进行分析,同时将本文提出的两种算法与常用社团划分算法进行了对比。实验结果表明本文提出的两种算法不仅具有较高的划分精度,而且在运行效率方面也有着较好的表现。
【关键词】：复杂网络 社团划分 相似度 三元社团 标签传播
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-6
• ABSTRACT6-13
• 第一章 绪论13-21
• 1.1 研究背景及意义13-15
• 1.1.1 研究背景13-14
• 1.1.2 研究意义14-15
• 1.2 国内外研究现状15-17
• 1.3 论文主要研究内容17-18
• 1.4 论文组织结构18-21
• 第二章 相关理论与技术21-29
• 2.1 复杂网络相关理论21-24
• 2.1.1 复杂网络的表示方法21-22
• 2.1.2 复杂网络的统计特征22-24
• 2.2 社团结构相关理论24-27
• 2.2.1 社团结构的定义24-26
• 2.2.2 模块度定义26-27
• 2.3 本章小结27-29
• 第三章 常用社团划分算法研究29-45
• 3.1 基于优化的算法29-36
• 3.1.1 Kernighan-Lin算法30-31
• 3.1.2 Fast Newman算法31-33
• 3.1.3 CNM算法33-36
• 3.2 基于启发式的算法36-41
• 3.2.1 GN算法36-39
• 3.2.2 快速分裂算法39-41
• 3.3 基于相似度的算法41-44
• 3.3.1 基于节点依赖度的算法41-44
• 3.4 本章小结44-45
• 第四章 基于相似度的三元社团合并算法45-55
• 4.1 问题描述45
• 4.2 算法演化模型45-46
• 4.3 算法介绍46-54
• 4.3.1 算法相关定义46-48
• 4.3.2 算法核心思想48
• 4.3.3 算法具体执行步骤及示例48-53
• 4.3.4 算法伪代码及复杂度分析53-54
• 4.4 本章小结54-55
• 第五章 基于三元社团的LPA算法55-63
• 5.1 传统LPA算法55-56
• 5.2 问题描述56-58
• 5.3 算法介绍58-61
• 5.3.1 算法相关定义及规则58-59
• 5.3.2 算法核心思想59
• 5.3.3 算法具体执行步骤及示例59-61
• 5.4 本章小结61-63
• 第六章 算法验证与分析63-75
• 6.1 实验数据集63-64
• 6.1.1 人工合成网络数据集63
• 6.1.2 真实世界网络数据集63-64
• 6.2 社团结构质量评价标准64-66
• 6.3 人工合成网络实验分析66-67
• 6.4 真实世界网络实验分析67-71
• 6.4.1 Zachary空手道俱乐部成员关系网络67-70
• 6.4.2 美国大学足球联赛网络70-71
• 6.5 算法比较分析71-73
• 6.6 本章小结73-75
• 第七章 总结与展望75-77
• 7.1 总结75-76
• 7.2 展望76-77
• 参考文献77-81
• 致谢81-83
• 攻读硕士学位期间已发表或录用的论文83

【相似文献】

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

1 冷明平;孙凌宇;郭恺强;边计年;朱平;;赋权超图划分算法的电路划分实验比较研究[J];计算机工程与应用;2012年16期

2 许金凤;董一鸿;王诗懿;何贤芒;陈华辉;;大规模图数据划分算法综述[J];电信科学;2014年07期

3 李莉杰;陈端兵;王冠楠;;有向网络重叠社区的快速划分算法[J];计算机科学;2014年S1期

4 卢风顺;宋君强;张理论;张卫民;任开军;朱小谦;;面向全球数值天气预报模式的加权等积并行数据划分算法[J];计算机研究与发展;2012年04期

5 喻云峰;赖海涛;;一种基于随机搜索的黑洞二划分算法实现[J];科技广场;2006年04期

6 李晨;葛声;;一种重叠可信社团划分算法的设计与实现[J];微计算机信息;2011年09期

7 李孝伟;陈福才;刘力雄;;一种融合节点与链接属性的社交网络社区划分算法[J];计算机应用研究;2013年05期

8 牛建军;刘上乾;韩宝君;任宝文;;同心圆检测中的区域划分算法[J];光子学报;2006年12期

9 吕德奎;;聚合算法在电力GIS中的应用[J];电力信息化;2012年05期

10 王晓芳;贾宗维;;一种新的图划分算法在PPI网络模块化中的研究[J];山西农业大学学报(自然科学版);2012年06期

中国重要会议论文全文数据库 前4条

1 王玲娜;李兴明;;基于最小支撑树的通用区域划分算法[A];2008年中国西部青年通信学术会议论文集[C];2008年

2 徐丹丹;章勇;;一种基于节点度更新的簇划分算法[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

3 刘培强;谢青松;朱大铭;;用于基因表达谱数据聚类分析的贪心图划分算法研究[A];2006年全国理论计算机科学学术年会论文集[C];2006年

4 刘华伟;全庆一;;能量有效的基于连通度的分布式簇划分算法[A];2011年全国通信安全学术会议论文集[C];2011年

中国硕士学位论文全文数据库 前10条

1 吴磊;复杂网络的社团划分算法研究[D];太原理工大学;2016年

2 马静;基于社交网络的社团划分算法研究[D];山东师范大学;2011年

3 韩明伟;超大规模集成电路划分算法研究[D];西安电子科技大学;2008年

4 许金凤;大规模动态自适应图划分算法[D];宁波大学;2015年

5 辛娟娟;社区划分算法的研究与应用[D];北京林业大学;2015年

6 杜鹏飞;基于边的相似性的复杂网络社团划分算法研究[D];山东师范大学;2014年

7 赵琴;并行计算中图划分算法的研究[D];华中师范大学;2013年

8 戴晓罡;复杂网络中的社团划分算法研究[D];南京邮电大学;2014年

9 林慧娴;个性化服务中用户建模及社区划分算法研究[D];南京邮电大学;2015年

10 王秀芹;软硬件协同设计中的划分算法研究[D];哈尔滨工程大学;2005年

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

，

本文编号：308843