Similarity graphs

Notes on the construction of similarity graphs in Matlab

Suppose your data is given by the matrix A (each row is a data point). Let the function d(x,y) be a distance measure between two data points. We can construct the distance matrix as follows:

Dist=zeros(size(A,1));
for i=1:size(A,1)
   for j=1:size(A,1)
       Dist(i,j)=d(A(i,:),A(j,:));
   end
end

To construct the weight matrix of an epsilon-neighborhood graph from a distance matrix.  Let ee = epsilon and set

W=ones(size(Dist));
W(Dist>ee)=0; % Set too far away to
W(Dist==0)=0;  % Avoid an edge to itself

The degree matrix can be build from an the weight matrix:

D=zeros(size(A,1));
for i=1:size(A,1)
    D(i,i)=sum(W(i,:));
end

Plotting a graph from a weight matrix

n=size(W,1);
z=exp(((1:n)-1)*2i*pi/n);
clf;
plot(z,'o','MarkerFaceColor','k'); % Plot all nodes
hold on;

for i=1:size(W,1)
   for j=1:size(W,1);
       if (W(i,j)>0)
            plot([z(i),z(j)],'k');   % Plot edges
       end
   end
end

The above codes plots the graph by placing nodes in a circle. MATLAB has built in functions for graphs, in particular plotting. The graph can also be plotted with the command

clf; plot(graph(W));

where the placement of the nodes is done in an automatic way.