graphmds_class

# Differences

This shows you the differences between two versions of the page.

 — graphmds_class [2012/10/25 14:56] (current)melancon created 2012/10/25 14:56 melancon created 2012/10/25 14:56 melancon created Line 1: Line 1: + ===== Visual Analytics Course ===== + ==== MDS (Multi-dimensional scaling) ==== + + This python code is meant to be used with the [[mds_class|''​MDS''​ class]]. You provide it a graph and a list of properties form which a dissimilarity matrix $\Delta$ 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) + ​ + + --- + + ​ + 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 +