دانلود رایگان مقاله آشفتگی نمودار و تغییرات طیفی مربوطه در توپولوژی اینترنت

abstract

The normalized Laplacian spectrum (NLS) is a powerful tool for comparing graphs with different sizes. Recently, we showed that two NLS features, namely the weighted spectral distribution (WSD) and the multiplicity of the eigenvalue 1 (ME1), are particularly relevant to the Internet topology at the inter-domain level. In this paper, we examine the physical meaning of the two metrics for the Internet. We show that the WSD reflects the transformation from single-homed nodes to multi-homed nodes for better fault-tolerance and that the ME1 quantifies the initial star-based structure associated with node classification, both of which are critical to the robustness of the Internet structure. We then investigate the relation between the metrics and graph perturbations (i.e., small changes in a graph). We show that these two NLS metrics can be a good choice for study on the Internet optimization. Our work reveals novel insights into the Internet structure and provides useful knowledge for statistical analysis on complex networks.

9. Conclusion

This paper focuses on the relation between graph perturbations and corresponding changes in the WSD and the ME1, and analyzes the physical meaning of the two spectral metrics embedded in Internet AS graphs, e.g., node classification, initial star-based structure, multihomed transformation and core-periphery decomposition. The two metrics reflect the NLS features with eigenvalues not only toward 0 (and 2) but also restricted to 1; i.e., they can be considered as the cost function representing the NLS. Additionally, they are independent of the network size of evolving AS graphs. Therefore, our contributions are useful for understanding the Internet structure and leading future applications of the NLS in AS graphs.