Description of mdsxy

Home > matgraph > @graph > mdsxy.m

mdsxy

PURPOSE

mdsxy(g) -- create an embedding based on multidimensional scaling

SYNOPSIS

function DD = mdsxy(g,D)

DESCRIPTION

 mdsxy(g) -- create an embedding based on multidimensional scaling
 
 This may also be invoked as mdsxy(g,D) where D is a distance matrix
 (i.e., the i,j entry of D is the desired distance between i and j). 
 The default is the graph-theoretic distance from i to j.

CROSS-REFERENCE INFORMATION

This function calls:

• dist dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
• embed embed --- create an embedding for a graph
• nv nv(g) --- number of vertices in g

This function is called by:

SOURCE CODE

0001 function DD = mdsxy(g,D)
0002 % mdsxy(g) -- create an embedding based on multidimensional scaling
0003 %
0004 % This may also be invoked as mdsxy(g,D) where D is a distance matrix
0005 % (i.e., the i,j entry of D is the desired distance between i and j).
0006 % The default is the graph-theoretic distance from i to j.
0007 
0008 % if the user does not
0009 if nargin == 1
0010     D = dist(g);
0011 end
0012 
0013 % any distances > cutoff  are truncated to cutoff.
0014 
0015 cutoff = 10;
0016 [i,j] = find(D>cutoff);
0017 m = length(i);
0018 for k=1:m
0019     D( i(k), j(k) ) = cutoff;
0020 end
0021 
0022 
0023 
0024 % rescale the D matrix so that the smallest positive entry is 1
0025 
0026 vals = D(:);
0027 vals = sort(vals);
0028 vals = vals(vals>0);
0029 minval = vals(1);
0030 D = D/minval;
0031 
0032 
0033 % find embedding vectors
0034 D = D.^2;
0035 n = nv(g);
0036 
0037 d1 = sum(D)/n;
0038 d2 = sum(d1)/n;
0039 
0040 u = ones(1,n);
0041 
0042 D1 = u'*d1;
0043 D2 = d2 * ones(n,n);
0044 
0045 Dstar = (-1/2) * (D - D1 - D1' + D2);
0046 
0047 [v,d] = eig(Dstar);
0048 d = real(d);
0049 v = real(v);
0050 dvec = (diag(d));
0051 [dvec,idx] = sort(-dvec);
0052 
0053 a = idx(1);
0054 b = idx(2);
0055 
0056 Lambda = d([a,b],[a,b]);
0057 sqrt(Lambda);
0058 xy = v(:,[a,b])*sqrt(Lambda);
0059 
0060 
0061 embed(g,xy)
0062 
0063 if nargout > 0
0064     DD = Dstar;
0065 end

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003