Drawing the AS Graph in 2.5 Dimensions

We propose a method for drawing AS graph data using 2.5D graph visualization. In order to bring out the pure graph structure of the AS graph we consider its core hierarchy. The k-cores are represented by 2D layouts whose interdependence for increasing k is displayed by the third dimension. For the core with maximum value a spectral layout is chosen thus emphasizing on the most important part of the

AS graph. The lower cores are added iteratively by force-based methods. In contrast to alternative approaches to visualize AS graph data, our method illustrates the entire AS graph structure. Moreover, it is generic with regard to the hierarchy displayed by the third dimension. 1 Introduction Current research activities in computer science and physics are aiming at under- standing the dynamic evolution of large and complex networks like the physical internet, World Wide Web, peer-to-peer systems and the relation between autonomous systems (AS). The design of adequate visualization methods for such networks is an important step towards this aim. As these graphs are on one hand large or even huge, on the other hand evolving, customized visualizations concentrating on their intrinsic structural characteristics are required. In this paper we propose a layout method that brings out the pure structure of an autonomous systems (AS) graph. More precisely, we focus on the core hierarchy of AS graphs. A 2D layout is obtained by first choosing a spectral layout to display the core with maximum value and then adding the lower cores iteratively by force-based methods. Using 2.5D graph visualization, we then rep- resent the core hierarchy by stacking the induced 2D layouts of the k-cores for increasing k on top of each other in the third dimension. Visualizations in 2.5D have been proposed frequently for network data, for example to display other graph hierarchies [6, 9] or evolving graphs over time [4]. A few samples of visualizations of AS graphs are already available. However, they either focus on the geographic location of the AS [8], on the routing struc- ture seen from a selected AS [2, 7] or on a high level view created by clustering star The authors gratefully acknowledge financial support from DFG under grant WA 654/13-2 and BR 2158/1-2, and from the European Commission within FET Open Projects COSIN (IST-2001-33555) and DELIS (contract no. 001907). J. Pach (Ed.): GD 2004, LNCS 3383, pp. 43–48, 2004. c© Springer-Verlag Berlin Heidelberg 2004 44 Michael Baur et al. the nodes [13]. In contrast, our method displays the entire AS graph structure without using external information. Previous attempts to analyze the structure of the AS graph propose the existence of meaningful central nodes that are highly connected to a large fraction of the graph [11]. It seems that this structural peculiarity is interpreted very well by the notion of k-cores...

Website: www.inf.uni-konstanz.de | Filesize: -
No of Page(s): 6
Download Drawing the AS Graph in 2.5 Dimensions.pdf