Sampling Internet Topologies: How Small Can We Go?
Vaishnavi Krishnamurthy, Sun Jun-hong, Michalis Faloutsos, Sudhir Leslie Tauro · 2003
In this paper, we develop methods to "sample " a large real network into a small realistic graph. Although topology modeling has received a lot attention lately, it has not yet been completely resolved. Several methods create arguably realistic topologies from scratch. Our approach moves in the exact opposite direction. First, we observe that many real topologies are available to the networking community. However, their size makes them expensive to use in simulations as is. This brings up the following question: how can we shrink a graph, so that it still retains its essential properties? We propose an iterative sampling framework and seven different "sampling" methods. We show that some of our methods can be very effective: they reduce a graph by 70%, and maintain several topological properties within 22% of the expected value. An advantage of this method is that it can potentially maintain topological properties that we are not yet aware: all we have to is sample "fairly". In addition, our methods are statistically robust and reliable. We find that apart from its practical applications, the problem of graph sampling is of interest in its own right.