New families of internet topology generators, typified by Brite and Inet,
are primarily trying to match the skewed degree sequence statistics
of the internet topology at the AS level.
(a) We have developed algorithms that, given a target degree sequence,
produce topologies meeting the degree sequence but differing substantially
from each other and from the real data. We can also produce ``random''
instances matching the real data. Our techniques use graph theoretic
primitives as well as the Markov chain simulation method,
and substantially enrich the output of existing generators.
(They also suggest that degree sequence alone is not sufficient to capture
all topology characteristics).
(b) For modeling and simulation purposes, it is particularly important
to identify global characteristics of AS topologies, such as hierarchy
and clustering. Hierarchy has been addressed in several prior works.
In this work we initiate a study of clustering using spectral filtering
(Singular Value Decomposition - Principal Vector Analysis) methods.
We have identified many clusters on the real data (expressing geography
or business and cutting across different hierarchical levels).
Synthetic data appear to posses significantly weaker clustering properties.
Joint work with Chitsos Gkantsidis, Amin Saberi, and Ellen Zegura.
Copyright. All Rights Reserved.