P.B.: The connectivity and fault-tolerance of the internet topology

In this paper, we apply data mining analysis to study the topology of the Internet, thus creating a new processing framework. To the best of our knowledge, this is one of the rst studies that focus on the Internet topology at the router level, i.e., each node is a router. The size (280K nodes) and the nature of the graph are such that new analysis methods have to be employed. First, we suggest computationally-expensive metrics to characterize topological properties. Then, we present an ecient approximation algorithm that makes the calculation of these metrics possible. Finally, we demonstrate the initial results of our framework. For example, we show that we can identify \central " routers, and poorly connected or even isolated nodes. We also nd that the Internet is surprisingly resilient to random link and router failures, having only small changes in the connectivity for fewer than 10,000 failures. Our framework seems a promising step towards understanding and characterizing the Internet topology and possible other real communication graphs such as web-graphs.