Multidimensional Scaling in Gephi

Multidimensional Scaling (MDS) is a data analysis technique that seeks to represent distances (similarities or dissimilarities) among a set of entities in a low-dimensional space in a way that entities that are more proximate to each other are also closer to each other in the low-dimensional space, and that entities that are less proximate to each other are further away from each other in the low-dimensional space (Wasserman & Faust 1994).

In Social Network Analysis (SNA) MDS is sometimes used to create a layout for the nodes in a graph that corresponds to distances between the nodes. In principle, any type of similarity or dissimilarity between the nodes can be used as the basis for determining their relative distances. A commonly used approach is to use the geodesic distances between the nodes as input for MDS. The MDS Statistics plugin for Gephi uses this approach. It calculates the geodesic distances between all nodes in a graph and then feeds these into the Stress Minimization algorithm of the MDSJ library that was created by the Algorithmics Group of the University of Konstanz (see reference below). The plugin reports a stress value and it adds the coordinates of the MDS configuration to the nodes list of the graph for which the analysis is done. The plugin can create configurations with up to ten dimensions. In the process, a weight matrix is used to determine how much the distance of pair of nodes contributes to stress (weight[i][j]  = distance[i][j]^exponent). An exponent of 0 or-2 is used, the latter of which is the common choice. The results can be plotted with a separate MDS Layout plugin. This plugin simply takes coordinates on two dimensions and uses these to make a layout for your graph. The distances can be scaled up or down to improve the readability of the graph.

Since Gephi was updated to version 0.9, the plugins can only be found from within the Gephi program itself, as far as I know. However, there should be a new online market place at some point. To download the latest version of the plugins (for Gephi 0.9 and higher), run Gephi, enter the ‘Tools’ menu in the menu bar at the top, and click ‘Plugins’. The MDS Statistics and MDS Layout plugins should be in the list of available plugins, and can be installed from there. An older version(for Gephi 0.8.2) of the MDS Statistics plugin and the MDS Layout plugin is still available from the original Gephi Market Place if required. I recommend using the new version of the plugins, but if you have good reasons for running Gephi 0.8.2, instead of the latest version, then the 0.8.2. version of the plugins can be downloaded and installed manually (download the .nbm file, go to the plugins menu within Gephi [see instructions above], select ‘Downloaded’, and then select the downloaded .nbm file).

If you use one of these plugins, I would appreciate that you also cite the software:

  • Spekkink, W. (2015). MDS Statistics [software]. Available from: https://marketplace.gephi.org/plugin/mds-statistics/
  • Spekkink, W. (2015). MDS Layout [software]. Available from: https://marketplace.gephi.org/plugin/mds-layout/

In addition, I think it will be appreciated if you cite the Algorithmics group of the University of Konstanz responsible for developing the wonderful MDSJ library. Without that library, I would definitely not have been able to develop the MDS Statistics plugin.

References:

  • Wasserman, S. and Faust. K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
  • Algorithmics Group. MDSJ: Java Library for Multidimensional Scaling (Version 0.2). Available at http://www.inf.uni-konstanz.de/algo/software/mdsj/. University of Konstanz, 2009.