Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications

    

1.  ABSTRACT :

 

                                  Comparing graphs to determine the level of underlying structural similarity between them is a widely encountered problem in computer science. It is particularly relevant to the study of Internet topologies, such as the generation of synthetic topologies to represent the Internet’s AS topology. We derive a new metric that enables exactly such a structural comparison, the weighted spectral distribution. We then apply this metric to three aspects of the study of the Internet’s AS topology. (i) we use it to quantify the effect of changing the mixing properties of a simple synthetic network generator. (ii) we use this quantitative understanding to examine the evolution of the Internet’s AS topology over approximately 7 years, finding that the distinction between the Internet core and periphery has blurred over time.(iii) we use the metric to derive optimal parametrization of several widely used AS topology generators with respect to a large-scale measurement of the real AS topology.

 2. EXISTING SYSTEM :

                                        Many techniques exist for graph comparison, e.g., the

edit distance (the number of link and node additions required to turn one graph into another), or counting the number of common substructures in two graphs. However, for large graphs such as the AS topologies examined here, these methods are computationally too expensive. In addition, they are inappropriate for dynamic graphs, resulting in varying edit distances or substructure counts. Instead, we require a metric which reflects the structure of large graphs in some

meaningful sense. Typical currently used “metrics” include the clustering coefficient, the assortativity coefficient, the node degree distribution and the k-core decomposition. However, these are not metrics in the mathematical sense, but rather are measures, e.g., two graphs may have the same clustering coefficient but hugely different structures. This distinction is important as a measure cannot be used to determine unique differences between graphs : two graphs with the same measures may not in fact be the same.

    3. PROPOSED SYSTEM :

                                          A new metric, the weighted spectral distribution (WSD). The WSD differs from other graph measures such as the clustering and assortativity coefficients, the node degree distribution, etc, in that it is a metric in the mathematical sense, and so it can be used to measure the distance between two graphs. The WSD has many applications, and in particular can be used for very large graphs because of its low computational requirements, making it a good choice for topology tuning and other applications that require multiple evaluations of a cost function. We presented three applications of the WSD, using it to understand:

                i) The mixing properties of graphs,

                ii) The evolution of the AS topology, and                                                        

                iii) the tuning of Internet topology generators to match a target graph.

                            The WSD is based on the spectrum of the normalized Laplace matrix and is thus strongly associated with the distribution of random walk cycles in a network . The probability of randomly walking N steps from a node such that we return to that node, indicates the connectivity of that node. Hence, a low probability indicates high connectivity (there are many routes, few of which return) while a high probability indicates high clustering (many of the routes lead back to the original node).The considerations for the work are to be:

(i)   a spectral metric and a straw man model for comparing the structure of large graphs;

(ii)  the analysis of more than 7 years of the evolution of the Internet AS topology seen from two different measurement techniques;

(iii)a comparison among the outputs of five major Internet topology generators and a measured data set; and

(iv)                Optimal parameter estimation of said topology generators with respect the measured data set using our metric.

4.HARDWARE REQUIREMENTS:

•         System                : Pentium IV 2.4 GHz.

•         Hard Disk            : 40 GB.

•         Floppy Drive       : 1.44 MB.

•         Monitor                : 15 VGA Colour.

•         Mouse                 : Logitech.

•         Ram                     : 256 MB.

   5.SOFTWARE REQUIREMENTS:

•         Operating System       : - Windows XP Professional.

•         Front End                               : - Asp .Net 2.0.

•         Coding Language       : - Visual C# .Net.