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