Statistical and Machine Learning Approaches for Network Analysis

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 ...