MDS-MAP

mds-map.m

% --- testcase: grid network ---
% A: adjacency matrix
inf = 999999;
w = 4;
h = 4;
A = inf*ones(w*h);
n = size(D,1);
for x = 1 : w
  for y = 1 : h
    if x < w
      i = x + w * (y-1);
      j = (x+1) + w * (y-1);
      A(i,j) = 1;
      A(j,i) = 1;
    end
    if y < h
      i = x + w * (y-1);
      j = x + w * y;
      A(i,j) = 1;
      A(j,i) = 1;
    end
  end
end
for i = 1 : n
  A(i,i) = 0;
end
% ---

% --- Multidimensional Scaling (MDS) ---
% compute all-pairs distance matrix by Floyd-Warshall
D = A;
for k = 1 : n
  i2k = repmat(D(:,k), 1, n);
  k2j = repmat(D(k,:), n, 1);
  D = min(D, i2k + k2j);
end

% compute inner-product matrix B
H = eye(n) - ones(n) / n;
B = -H * (D .* D) * H;

% extract top two eigenvectors
[P, lambda] = eigs(B,2);
x = sqrt(lambda(1,1)) * P(:,1);
y = sqrt(lambda(2,2)) * P(:,2);


% --- plot ---
% plot vertices
plot(x,y,'ro');
hold on;

% plot edges
[i,j,a] = find(A < inf);
for k = 1 : size(j,1)
  plot(x([i(k),j(k)]), y([i(k),j(k)]), '-b');
end
hold off;