Big-bangsimulationforembeddingnetworkdistancesinEuclideanspace.pdfVIP

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 6, DECEMBER 2004 993 Big-Bang Simulation for Embedding Network Distances in Euclidean Space Yuval Shavitt, Senior Member, IEEE, and Tomer Tankel, Student Member, IEEE Abstract—Embedding of a graph metric in Euclidean space effi- process and to reduce the representation, IDMaps suggests using ciently and accurately is an important problem in general with ap- a smaller number of measurement points, Tracers, that mea- plications in topology aggregation, closest mirror selection, and ap- sure distances among themselves and then using them as a ref- plication level routing. We propose a new graph embedding scheme erence distance map to the other network regions. called Big-Bang Simulation (BBS), which simulates an explosion of particles under a force field derived from embedding error. BBS A relatively new approach to represent a network distance is shown to be significantly more accurate compared to all other matrix is to map network nodes into points in a real Euclidean embedding methods, including GNP. We report an extensive sim- space. Such a mapping is designed to preserve the distance be- ulation study of BBS compared with several known embedding tween any pair of network nodes close to the Euclidean distance schemes and show its advantage for distance estimation (as in the between their geometric images. Such a mapping is called an IDMaps project), mirror selection, and topology aggregation. embedding, and the