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.
No comments:
Post a Comment