面向AS级Internet网络拓扑的正规Laplacian图谱稳定不变特征及其建模、仿真与评估技术

Random graph, hierarchy structure and nodes degree are the typical models for the simulation of the AS-level Internet topology. However, those models are the simple descriptions of the corresponding network structure, which induces the inaccuracy of the synthetic graphs on the metrics associated with local connectivity. With spectral graph theory, the normalized Laplacian spectrum (nls) is a more accurate model for the corresponding AS graphs and can be used to capture the characteristics of global nodes classification and local connectivity. Therefore, this program mines the stable properties of the nls with the Internet evolving. In addition, for the problem that it is difficult for the Internet test bed to match the scale of the real Internet with explosive growth of nodes, this program studies the modeling, simulation and evaluation methods for the AS-level Internet topology based on the nls, e.g. modeling the evolvement characteristics of the nls, optimizing the interactive growth mechanism and nodes preferential attachment models, mining the relationships between graph perturbation and corresponding changes in the nls, evaluating the fidelity of the synthetic AS graph with different topology metrics, etc. The results of this program will be significant for the topology simulation and corresponding fidelity evaluation of the Internet test bed with limit scale and the research for the development, test and evaluation methods of the Internet technology.

随机图、层次结构和节点度，是AS级Internet网络拓扑仿真的常用模型。然而，这些模型是相应网络结构的简化描述，导致仿真拓扑图在局部连通性等尺度上表现出不精确性。根据谱图理论，正规Laplacian图谱能够更精确地建模相应AS图结构的全局节点分类和局部连通性特征。因此，本项目深入挖掘正规Laplacian图谱在不同节点规模拓扑图演化过程中的稳定不变特征，并针对Internet测试床难以紧跟真实Internet爆炸式节点规模增长趋势的现实问题，从图谱演化建模、交互增长与节点偏好连接模型优化、图扰动与图谱变化关联挖掘、逼真度综合评估等方面，开展基于正规Laplacian图谱的AS级Internet网络拓扑建模、仿真与评估方法的研究。研究成果，对于限定节点规模条件下的Internet测试床拓扑结构仿真及其逼真度综合评估，以及Internet技术开发、测试与评估方法的研究等，具有重要意义。

真实Internet正在以指数级的规模增长趋势不断演化。因此，捕获其拓扑与节点规模无关的结构属性，对于其演化机理的认知与规模压缩理论的研究等具有重要意义。本项目以正规Laplacian图谱为价值函数，对自治系统（AS, Autonomous System）级Internet拓扑与规模无关结构特征的物理意义展开深入地研究。具体地，我们以特征值1重复度（ME1, The multiplicity of the eigenvalue 1）和加权谱分布（WSD, Weighted spectral distribution）表征正规Laplacian图谱。其中ME1表示特征值1的总数，而WSD表征远离1特征值分布的加权和。我们的创新工作证明，ME1定量统计AS级Internet拓扑的内核-外围分解特征，且WSD指示该拓扑从Single-homed向Multi-homed的转变过程。此外，我们给出了ME1（和WSD）与节点总数比率严格地无关于节点规模的理论与数值证明，并设计了这两个图谱属性的线性时间复杂性的快速计算方法，使得它们可以被应用于百万以上节点的大规模Scale-free网络系统；进一步地，我们证明WSD与节点总数的比率在更普遍的演化系统是平均路径长度的良好指示器，且该比率严格指示着网络中度较小节点之间的多边形连接关系。在未来工作中，我们将以正规Laplacian图谱表征的Internet拓扑独有的结构属性为基础，开展AS级拓扑采样技术的研究，并结合Internet测试床的任务需求，力争实现测试床节点规模的大比例规模缩减。