User Tools

Site Tools


graphmds_class

Visual Analytics Course

MDS (Multi-dimensional scaling)

This python code is meant to be used with the ''MDS'' class. You provide it a graph and a list of properties form which a dissimilarity matrix is computed. The matrix can then be passed on to the MDS class to compute a (usually) 2D embedding for the graph. You would typically use it as:

gMDS = GraphMDS(graph, ['propertyName1', ...]
 
mds = MDS(gMDS.dissimilarityMatrix)
gMDS.layout(mds)

GraphPCA.py
from tulip import *
from numpy import *
from MDS import *
 
class GraphMDS(object):
    '''
    This is a utilitary class to the MDS class.
    It builds a dissimilarity matrix data from several graph (double) properties.
    The matrix can then be handled to the MDS class to perform MDS projection.
 
    Note: all properties used by the class must have been pre-computed.
    '''
 
    def __init__(self, graph, propertyNameList):
        '''
        Constructor
        '''
        self.graph = graph
        self.viewLayout = self.graph.getLayoutProperty('viewLayout')
        self.propertyNameList = propertyNameList
        self.propertyList = []
        for i in range(len(self.propertyNameList)):
            self.propertyList.append(self.graph.getDoubleProperty(self.propertyNameList[i]))
        m =[]
        for n in self.graph.getNodes():
            nVect = []
            for p in self.propertyList:
                nVect.append(p.getNodeValue(n))
            #print nVect
            m.append(nVect)
        self.dataMatrix = array(m)
        self.uno = array([1] * self.dataMatrix.shape[0])
        self.barycenter = None
        self.__computeNormalizedMatrix__()
        self.dissimilarityMatrix = self.__dissimilarityMatrix__()
 
    def __computeBarycenter__(self):
        self.barycenter = dot(transpose(self.dataMatrix), dot(self.weights, self.uno))
        return True
 
    def __computeNormalizedMatrix__(self):
        '''
        Data normalization
        '''
        if self.barycenter == None:
            self.__computeBarycenter__()
        Y = self.dataMatrix - self.__dotVector__(self.uno, self.barycenter)
        d = zeros([self.dataMatrix.shape[1], self.dataMatrix.shape[1]])
        for i in range(self.dataMatrix.shape[1]):
            d[i, i] = 1.0 / std(self.dataMatrix[:, i])
        self.normalizedDataMatrix = dot(Y, d)
        return True
 
    def __dissimilarityMatrix__(self):
        '''
        Dissimilarities are induced from Euclidean distances between nodes
        based on attributes (properties passed on as parameters when instantiating the class
        '''
        self.__computeBarycenter__()
        self.__computeNormalizedMatrix__()
        m = matrix([[0] * self.normalizedDataMatrix.shape[0]] * self.normalizedDataMatrix.shape[0])
        for i in range(self.normalizedDataMatrix.shape[0]):
            m[i, i] = 0.0
            for j in range(i+1, self.normalizedDataMatrix.shape[0]):
                m[i, j] = self.__distance__(self.normalizedDataMatrix[i], self.normalizedDataMatrix[j])
                m[j, i] = m[i, j]
        return m
 
    def __distance__(self, vect1, vect2):
        d = 0.0
        for i in range(len(vect1)):
            d += (vect1[i] - vect2[i])**2
        return sqrt(d)
 
    def layout(self, mds):
        '''
        Assumes an MDS object has been created using the dissimilarity matrix
        computed by the __dissimilarityMatrix__ method.
 
        Ideally, the GraphMDS class should have its own internal MDS class,
        but for some (still unclear) reason this has not been posisble.
        '''
        xCoords = mds.embeddingMatrix[0,:]
        yCoords = mds.embeddingMatrix[1,:]
	i = 0
	for node in self.graph.getNodes():
		cNode = self.viewLayout[node]
		cNode.setX(xCoords[i])
		cNode.setY(yCoords[i])
		self.viewLayout[node] = cNode
		i += 1
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/graphmds_class.txt · Last modified: 2012/10/25 14:56 by melancon