K-core Decomposition And Modeling On Internet Router-level Topology

Being a typical instance of complex network, the research and modeling on Internet topology has become a hot topic at present and attracted more and more attention of academia. In recent years, researches in this field have made considerable progress, especially in the autonomous system level (AS-level) Internet topology. However, because of the complexity of Internet router-level topology, people have not got a clear understanding on it up to now. There are still some laws in this seemingly chaotic network that we have not known, and need us to further excavate. The research and modeling on the hierarchy of Internet router-level topology can help people better understand the characteristics of Internet basic architecture, which will bring great effect on the design of the next generation of Internet and the research on the protocol systems related with Internet.Firstly, the k-core decomposition of Internet router-level topology was analyzed in the paper. By analyzing the measuring data of CAIDA monitors in May 2007, it has been found that the k-core structures of the topologies measured by the various monitors are similar with that of the whole topology, which indicates that sample bias has a little effect on the k-core structure of Internet. The further analysis on the measuring data of Riesling monitor from Jau 2006 to Dec 2006 shows that the the k-core structure of Internet changes little with the evolution of time. As time went by, only the size of the topology coreness changes, while the distribution law of the nodes in each k-core remains unchanged. After that, we analyzed the relationship between the node degree and node coreness on qualitation and quantitation. The results show that there is no evident relation between them.Secondly, a detailed analysis of the hierarchy characteristics of Internet router-level topology was given. Taking k-core decomposition as main method, by analyzing the actural data measured by CAIDA, it is indicated that Internet router-level topology has evident hierarchical structure:from inner hierarchy to outer hierarchy, the nodes distribute from the highest coreness to the lowest. In the innermost hierarchy, the nodes distribute on only a few network addresses. From inner to outer, the distribution of the network addresses becomes more and more expanded, and the frequency-degree power law is increasingly finer. In the outmost hierarchy, the distribution of the network addresses is the widest and the power law is the finest.Thirdly, the fractal features of Internet router-level topology was studied based on k-core decomposition. By analyzing the main measurement quantities such as degree distribution, degree correlations and clustering coefficient of each k-core of the measuring data of CAIDA, it is shown that not only the degree distribution but also the clustering and correlations structures of Internet topology are essentially preserved as the more and more external parts of the network are pruned. This hints to a sort of global self-similarity for regions of increasingly approaching to the centrality of the network, and to a structure in which each region of the Internet as defined in terms of network centrality has the same properties with the whole network. The further analysis on the distribution of the spectral density with eigenvalues and signless Laplacian spectra(SLS) of each k-core shows that the results of them are highly coherence proving in another aspect that Internet topology has the property of self-similarity, which describes that the Internet topology has fractal characteristics.In the following chapter, the visualization on Internet router-level topology was studied. An algorithm based on k-core decomposition which evolved from inner core to outer core based on node coreness was proposed firstly, then the visualization results with the Internet topology measuring data of Riesling monitor of CAIDA in May 2007 was given. It can be seen from the visualization results that the algorithm is very outstanding on describing the hierarchy evolvement of the Internet topology, but this algorithm was not able to distinguish two or more disconnected components in the innermost core. So it was improved in the next content and the visualization results with the Internet topology measuring data of CAIDA in May 2007 was given. The visualization results show that the improved algorithm can present networks in which the highest k-core are composed by several connected components. Some characteristics, for example, clusterring and community, of Internet router-level topology can be seen from the evolvement results. By analyzing the complexity of the two algorithm, it can be seen that their running time is short and suit to the visualization of huge network.Finally, by analyzing the distribution of the nodes in each shell and the distribution of the links to the higher shells, a hierarchical model of Internet router-level topology based on k-core decomposition was proposed and realized. The analysis shows that this model can reproduce on Internet on most properties and has got topology coreness close to that of Internet. The experiments show that compared with the previous classical models, the model in the paper can fully reflects the hierarchy characteristics of Internet topology while preserving the power-law distribution of node degree.