Similarity graphs

Notes on the construction of similarity graphs

Suppose your data is given by the matrix A (each row is a data point). Let the function s(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)=s(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.