6.8 Internet Topology Evolution

The WSD produces a mapping from , where |K| = 71 bins are used in the examples in this section. However, a 71 dimensional space is still too large to effectively visualize clustering across graphs. In this section, we introduce multidimensional scaling (MDS), a technique mapping the WSD into a lower dimension.

Specifically, given C different graphs we seek a mapping from their WSD's into an l dimensional space: where l < < |K|. Typically l = 2 or 3 makes visual inspection most straightforward. Note that the methods used are parameter-free and so a natural clustering of the data is sought, as opposed to a supervised method which applies a mapping learned from training data.

Multidimensional scaling [38] is a technique mapping distances between objects into a reduced dimensional space. An intuitive example involves taking the distance matrix commonly shown in the bottom corner of many road maps and using it to reconstruct the map itself. The technique uses distance between the graphs here defined in terms of the metric introduced in Equation (6.16), ℑ(G₁, G₂, N). First, a dissimilarity matrix, R, is constructed as

(6.24)

The goal of MDS is to find a set of vectors Z₁, Z₂, . . ., Z_|K| that incrementally approximate the distance in the dissimilarity matrix. Specifically, we wish to minimize the distance between the projected vectors and the original data as

(6.25)

where C is the cost function to be minimized. We then perform the minimization using numerical optimization based on the eigenvector decomposition of R[39]. Typically, the first and second vectors, Z₁ and Z₂, are sufficient to allow visualization of clustering within the data.

Figure 6.19 shows the evolution of the Internet AS topology over time, as observed in the UCLA dataset described in Section 6.4.3. It is difficult to discern any consistent evolution from the raw WSD plots in Figure 6.19a. However, applying the MDS to reduce the dimensionality from 71 to 2 results in Figure 6.19b, in which each point represents the projection of a computed WSD for a given topology, that is, the WSD computed for a given month's observations in the UCLA dataset. Note that the axes are dimensionless, it is not the particular values that are important but the separation of points computed.

Figure 6.19 Structural evolution of the Internet via raw WSD and WSD with MDS applied. (a) Raw WSDs. (b) WSDs after applying MDS.

Interestingly, plotting with an arrow joining consecutive points, that is, an arrow connects the points for datasets 1 and 2, another connects points for datasets 2 and 3, and so on, shows that the evolution of the WSD for the topology appears to be consistent over time, it represents the “structural walk” of the Internet AS topology observed by the UCLA data. The lack of clustering of points around a center suggests the structure of the Internet is evolving in some way. This evolution is very difficult to see by directly comparing the WSD lines but can easily be observed using this multidimensional scaling technique. This is much more straightforward than the current alternative approach which would involve using a complex set of topological measures to distinguish the different graphs [40]. The reason for this actual evolution is better examined in a different domain; for the interested reader we recommend reading [41]. Here, the aim is merely to show that MDS used in conjunction with WSD can be used to track the structural changes in a network.