User Tools

Site Tools


graphmds_class

Differences

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

Link to this comparison view

graphmds_class [2012/10/25 14:56] (current)
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:
 +
 +<code python>
 +gMDS = GraphMDS(graph,​ ['​propertyName1',​ ...]
 +
 +mds = MDS(gMDS.dissimilarityMatrix)
 +gMDS.layout(mds)
 +</​code>​
 +
 +---
 +
 +<code python 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
 +</​code>​
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/graphmds_class.txt · Last modified: 2012/10/25 14:56 by melancon