Search code examples
matlabsparse-matrixadjacency-matrix

Calculating the degree matrix having the sparse representation of the adjacency matrix

I am trying to calculate the laplacian matrix of a graph. I ve calculated the sparse representation of the adjacency matrix which is stored in a text file with dimension Nx3. N the size of nodes (ith-node jth node weight). I open in Matlab this file with adj = spconvert(adj);. The next step is to calculate the degree matrix of this sparse matrix in order to perform the operation L = D - adj. How is it possible to calculate the degree matrix having as an input the sparse adjacency matrix of the graph? In order to calculate the degree matrix I calculate the degree for every node:

for i=1:n % size of the node
    degree(i) =  length(find(adj(:,1) == i & adj(:,3) == 1));
end

However, how can I perform the subtraction of D and A?

Solution

  • Use the spdiags function to convert the degree vector to a sparse diagonal matrix. Then subtract the adjacency matrix from diagonal matrix to get the Laplacian. Example using your code:

    adj = spconvert(adj);
for i=1:size(adj, 1)
    degree(i) = CalcDegree(adj, i)
end
D = spdiags(degree, 0, size(adj, 1), size(adj, 2));
L = D - adj;

    By the way, your code for calculating the node degree may be incorrect.