费德勒向量极值分析与复杂网络加边算法研究

论文摘要

随着计算机和互联网的快速发展,社交网络和计算机网络等实际网络的规模正在急剧增加,网络中不可避免的会有新的边（链接）增加,因此,加边扩容问题成为网络动态演化过程中结构变化的一个重要研究课题。加边扩容算法主要研究根据不同的优化目标设计最优的加边策略,大数据时代,随着网络规模增大,结构复杂性增加,完全基于网络结构的研究方法和结论显然不能满足现实应用中的需求,因此需结合网络的多种相关理论设计加边算法。本文分析了费德勒向量与图结构的关系,从代数的角度研究了网络的结构性质,并提出了快速有效的最大化代数连通度和传输容量的加边算法,另外,还结合社会科学中的结构洞理论提出了最小化网络平均最短路径的加边算法,本文旨在为大规模网络扩容提供高效可行的加边算法,同时为多角度研究网络结构提供思路。具体工作包括以下四个方面:1、本文进一步研究了费德勒向量与图结构的关系。费德勒向量（Fiedler Vector）是图的拉普拉斯矩阵的第二小特征值对应的向量,其在图的分割,数据聚类,社交网络等领域有着广泛的应用,费德勒向量的重要意义在于其把图的代数特征（如拉普拉斯矩阵的特征值和特征向量）与图的拓扑结构特征（如图的连通性等）联系起来,使得人们可以通过特征向量分量的大小,正负等来研究图的结构,比如,费德勒向量分量的非负的值对应图顶点的导出子图是连通的。因此,费德勒向量常常被用于网络结构研究。本文的具体研究成果如下:首先,本文定义了-匹配图,这种图的最小度点恰恰对应了费德勒向量分量的最大值。并且我们证明了树图是-匹配图。进一步的抽样统计实验表明大部分图都是-匹配图。然后,本文给出了Fiedler-Breadth-First图的定义,这类图的特点是:如果以费德勒向量分量的最大值对应的顶点为根生成广度优先图,则费德勒向量分量的最小值一定在该图的最高层。为了验证该图类的存在性,本文找到并证明了一类这样的图。同样抽样统计实验表明大部分图都是Fiedler-Breadth-First图。2、根据费德勒向量与图结构的关系设计了最大化代数连通度的算法。代数连通度是图拉普拉斯矩阵的第二小特征值,是多智能体等网络系统的基本性能指标。本文讨论了如何通过最大化代数连通度来增加网络的连通性和鲁棒性。目前已有的代数连通度最大化的有效算法需要直接计算它,这导致算法复杂度较高,难于应用在大规模的现实网络。本文在分析费德勒向量的基础上,提出了一种不需要计算代数连通度的启发式算法――最小度和最大距离（MDMD）算法。该算法在大型随机网络和现实自主系统（AS）对等信息网络中进行了测试。仿真结果表明,该算法是有效的,与其他算法相比,有更短的运行时间。因此,它可以应用于非常大的网络,特别是大型稀疏网络。3、研究了代数连通度与传输容量的关系,并提出了最大化网络传输容量加边算法。本文研究了如何通过加边来提高无标度网络的传输效率。在分析了代数连通度与传输容量之间相关性的基础上,提出了一种有效的加边策略:最大化代数连通度增量边（MACIE）算法。现有的方法大都基于拓扑结构指标,如网络的路径和度,而MACIE算法从网络的代数属性与结构指标关系角度研究和设计提高传输效率的算法,因此具有更短的运行时间。仿真结果表明,MACIE算法是有效的,其性能优于以往的减少结构孔（RSH）的策略。4、应用社会学中结构洞理论设计了最小化平均最短路径长度算法。平均最短路径长度是网络的小世界特性的一个衡量指标,网络具有小世界特性,意味着平均最短路径较小。网络的动态演化过程,是一个小世界化的过程,因此如何加边,使得网络平均最短路径最小化有重要应用意义。本论文基于社会学中的结构洞理论设计了加边算法,该算法的核心思路是连接网络中结构洞数目最多的顶点。结构洞数目较多的顶点意味着有较多的路径通过,连接这样的点可以影响尽可能多的最短路径,因此可以有效减小平均最短路径长度。对比试验验证了我们算法的有效性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 选题背景和意义
•   1.2 费德勒向量研究概述
•     1.2.1 费德勒向量理论研究概述
•     1.2.2 费德勒向量应用举例
•   1.3 复杂网络加边算法研究概述
•     1.3.1 问题描述
•     1.3.2 最大化代数连通度的加边算法
•     1.3.3 最大化网络传输容量的加边算法
•     1.3.4 最小化平均最短路径的加边算法
•     1.3.5 基于顶点中介中心性的加边算法
•     1.3.6 其他加边算法
•   1.4 本文主要工作
•   1.5 论文组织结构
• 第二章 数学基础与基础理论
•   2.1 图论基础
•   2.2 主要模型及参数
•     2.2.1 ER随机网络模型
•     2.2.2 BA无标度网络模型
•     2.2.3 流量模型
•     2.2.4 中介中心性（Betweenness Centrality）
•     2.2.5 结构洞理论（Structural Holes Theory）
•     2.2.6 相关系数
•     2.2.7 平均路径长度（Average path length）
•   2.3 本章小结
• 第三章 费德勒向量的极值研究
•   3.1 相关符号和定义
•   3.2 费德勒向量的研究现状与成果
•   3.3 费德勒向量极值的研究现状与成果
•   3.4 本论文关于费德勒向量极值的主要理论成果
•     3.4.1 （?）-匹配图
•     3.4.2 Fiedler-Breadth-First图
•   3.5 讨论
•   3.6 本章小结
• 第四章 基于费德勒向量极值的最大化代数连通度的加边算法
•   4.1 研究背景和意义
•   4.2 国内外研究现状及发展动态分析
•     4.2.1 问题的研究现状与成果
•     4.2.2 最大化代数连通度问题研究存在的问题
•   4.3 预备知识
•     4.3.1 问题定义
•     4.3.2 与本章相关的工作
•   4.4 最小度-最大距离（MDMD）算法
•     4.4.1 MDMD算法
•     4.4.2 MDMD算法的理论分析
•   4.5 数值实验
•   4.6 本章小结
• 第五章 基于代数连通度的最大化网络传输容量的加边算法
•   5.1 研究背景和意义
•   5.2 国内外研究现状及发展动态分析
•   5.3 预备知识
•   5.4 与本章相关的工作
•     5.4.1 软方法
•     5.4.2 减小结构洞策略（RSH）
•   5.5 MACIE算法
•   5.6 数值实验
•   5.7 本章小结
• 第六章 基于结构洞理论的最小化平均最短路径的加边算法
•   6.1 研究背景和意义
•   6.2 国内外研究现状及发展动态分析
•     6.2.1 问题的研究现状与成果
•     6.2.2 预备知识
•   6.3 相关工作
•   6.4 基于结构洞的平均最短路径优化算法
•   6.5 数值实验
•   6.6 本章小结
• 第七章 总结与展望
•   7.1 工作小结
•   7.2 未来工作展望
• 参考文献
• 攻读博士学位期间取得的研究成果
• 致谢
• 附件

文章来源

类型: 博士论文

作者: 李刚

导师: 郝志峰

关键词: 费德勒向量,代数连通度,网络优化,复杂网络,传输容量,平均路径长度

来源: 华南理工大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 华南理工大学

分类号: O157.5;TP301.6

DOI: 10.27151/d.cnki.ghnlu.2019.000055

总页数: 105

文件大小: 3639K

下载量: 116