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

发布时间：2017-07-28 17:06

  本文关键词：复杂网络中社团发现算法的研究

  更多相关文章： 大规模复杂网络 加权网模型 局部社团发现 边划分 社团中重要节点

【摘要】：复杂网络的研究是现今科学研究中的一个重要研究方向。复杂网络中存在着大量的社团结构。发现复杂网络中的社团结构是了解整个复杂网络结构和功能的重要途径。随着信息量的急剧增长,经典的社团发现算法由于时间复杂度高,已经无法完成大规模复杂网络的社团发现,研究准确度高且时间复杂度低的大规模复杂网络的社团发现算法迫在眉睫。由于社团中的重要节点在社团中具有很大的影响力,所以发现社团中的重要节点对网络的安全、控制和监管具有重要意义。然而常见的重要节点发现算法考虑因素片面单一,且是用于寻找全网中的重要节点,因此,就需要探索考虑因素周全的社团中重要节点的发现算法。经典的社团发现算法主要研究的是无权网。无权网无法体现出网络中节点之间的连接强度,且大多真实的网络是加权网。这些网络用加权网络模型描述更加合理,因此本文在对复杂网络进行社团发现前先对具有社团结构的加权网建模。考虑到两点间的连接次数、共同邻点的个数和点权的影响,本文建立了基于共同邻点的加权网模型。本文分别对3个标准测试网络用基于共同邻点的加权网模型建模,验证了此模型中节点的度和点权都符合幂律分布。目前大多数的社团发现算法利用全局模块度对节点进行社团划分,时间复杂度高,本文提出了基于邻边的局部社团发现算法。结合局部社团的邻边特性,本文提出了局部社团的判断函数,并对加权网的边进行社团划分,发现重叠社团。然后定义了重叠点的归属判断函数对重叠点进一步划化,从而得到非重叠社团。本文对3个标准测试网络和2个大规模网络用基于邻边的局部社团发现算法划分社团,并与经典的社团发现算法对比。仿真结果表明,本文算法不仅准确度高且时间复杂度低,大大提高了算法的执行效率,适合发现大规模复杂网络中的社团。在划分得到的社团中,发现社团中的重要节点。针对常见的重要节点发现算法考虑因素片面单一,本文结合节点的连接状态、节点在社团中的位置、节点的权重及其邻居节点的影响,提出了社团中重要节点的发现算法。本文定义了加权网中的接近度因子、度中心性因子和邻点影响的附加因素,提出了社团中节点的重要度函数,利用此函数发现社团中的重要节点。通过对3个标准测试网络和2个大规模网络的仿真,发现了社团中的重要节点。与常见的重要节点发现算法相比,本文算法更合理且易区分开节点的重要度,适合用于大规模的复杂网络中。
【关键词】：大规模复杂网络 加权网模型 局部社团发现 边划分 社团中重要节点
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-14
• 第一章 绪论14-20
• 1.1 研究背景与意义14-15
• 1.2 国内外研究现状15-17
• 1.3 本文的创新点17-18
• 1.4 本论文的结构安排18-20
• 第二章 复杂网络中社团发现算法的概述20-29
• 2.1 复杂网络的表示20-22
• 2.1.1 图的相关概念20-21
• 2.1.2 邻接矩阵21-22
• 2.2 复杂网络中的社团发现22
• 2.3 经典的复杂网络中的社团发现算法22-28
• 2.3.1 Kernighan-Lin算法22-23
• 2.3.2 谱平分法23-25
• 2.3.3 分裂算法25-27
• 2.3.4 凝聚算法27-28
• 2.4 本章小结28-29
• 第三章 具有社团结构的加权网的分析与建模29-42
• 3.1 加权网的分析29-32
• 3.1.1 度和点权29-30
• 3.1.2 加权网最短路径30-31
• 3.1.3 加权网集聚系数31-32
• 3.2 基于共同邻点的加权网模型32-41
• 3.2.1 构建分析34-36
• 3.2.2 模型演化36-39
• 3.2.3 模型建立39
• 3.2.4 模型分析39-41
• 3.3 本章小结41-42
• 第四章 基于邻边的局部社团发现算法42-69
• 4.1 经典社团发现算法存在的问题42-44
• 4.2 加权网的局部社团判断函数M44-48
• 4.3 发现重叠社团48-52
• 4.3.1 算法主要思想48-49
• 4.3.2 算法数据结构49-50
• 4.3.3 算法实现50-52
• 4.4 处理重叠点52-56
• 4.4.1 算法主要思想52-53
• 4.4.2 算法实现53-56
• 4.5 社团发现算法的评价指标56-57
• 4.5.1 共同信息比较函数I56
• 4.5.2 模块度函数Q56-57
• 4.5.3 算法的执行时间T57
• 4.6 算法仿真与分析57-68
• 4.6.1 Zachary网络57-60
• 4.6.2 Dolphins网络60-62
• 4.6.3 Scientist网络62-64
• 4.6.4 几种算法的比较64-67
• 4.6.5 大规模复杂网络67-68
• 4.7 本章小结68-69
• 第五章 社团中重要节点的发现算法69-85
• 5.1 常见的重要节点的发现算法69-70
• 5.1.1 度中心性69-70
• 5.1.2 接近度70
• 5.2 节点对社团的贡献70-71
• 5.3 社团中节点的重要度函数71-74
• 5.3.1 度中心性因子72
• 5.3.2 接近度因子72-73
• 5.3.3 邻点影响73-74
• 5.4 社团中重要节点的发现算法74-78
• 5.4.1 算法主要思想74-75
• 5.4.2 算法数据结构75
• 5.4.3 算法实现75-78
• 5.5 算法仿真与分析78-84
• 5.5.1 Zachary网络78-80
• 5.5.2 Dolphins网络80-82
• 5.5.3 Scientist网络82-83
• 5.5.4 大规模复杂网络83-84
• 5.6 本章小结84-85
• 第六章 总结与展望85-87
• 6.1 总结85-86
• 6.2 展望86-87
• 致谢87-88
• 参考文献88-92
• 研究生期间所获成果92-93

【二级参考文献】

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

1 张健沛;李泓波;杨静;白劲波;张乐君;初妍;;基于归属不确定性的变规模网络重叠社区识别[J];电子学报;2012年12期

2 郭崇慧;张娜;;基于共邻矩阵的复杂网络社区结构划分方法[J];系统工程理论与实践;2010年06期

，

本文编号：585081