Multidimensional Scaling

For a graph of n actors with any number of interactions between each actor, we are looking at an n-dimensional structure that cannot be graphically represented for n > 2. For that reason, we apply Multidimensional Scaling to the interaction matrix, in order to come up with a 2-dimensional graph that comes closest to the n-dimensional representation. Multidimensional Scaling attempts to minimize the strain between nodes while projecting the n-dimensional structure onto a 2-dimensional space.

Two approaches to MDS have been attempted. The first approach yielded a graph that somewhat satisfied the requirements of constructing a minimal-strain graph. The MDS graph was constructed by giving a first approximation of the layout, and then gradually adjusting nodes while minimizing the strain and maximizing the original edge weighting. The second, and finally utilized method uses Singular Value Decomposition in order to generate the graph with the best representation. SVD is typically used applications involving least squares, e.g. curve fitting. This approach was motivated by an application named "Cloogle" that can be found at http://www.lans.ece.utexas.edu/~strehl/lsdm/. After preparing the original distance matrix, the MDS algorithm applies SVD and finally uses the first two columns in the resulting square matrix as (x,y) coordinates for the nodes. If we had a higher order method of displaying the nodes, we would use columns 3 and higher. Had we only 1 dimension for displaying the nodes, we would use column 1 for the best approximation.

Computation of MDS

Because the ActorGraphFrame as well as the ActorSceneLocationFrame can be scaled by the user, we do not wish to apply Multidimensional Scaling each time the size is changed. For that reason, once a ShotSpreadSheet has been opened and the data has been initialized, Multidimensional Scaling is applied to the distance matrix, resulting in a scaled version in a 2-dimensional region of (0,0) to (1,1). For each resized window, this version of the matrix is scaled up to the current size of the frame.