# Problem with R code for spectral clustering

am writing a simple R script to test the spectral clustering algorithm but for the eigenvalues I don't get them all positive and lambda0 is different from 0. here is my script

Dsqrt<-matrix(0,length(V(g)),length(V(g)))  # The D^-0.5 matrix
for(i in 1:(length(V(g))-1))
Dsqrt[i,i]<-1/sqrt(degree(g,V(g)[i-1]))

L<-graph.laplacian(g, normalized=TRUE) #Here L[i,i]=1 and L[i,j]= 1/sqrt(d[i]*d[j])
L<-Dsqrt %*% L %*% Dsqrt
Eigns<-eigen(L)


And when I check Eigns$values sometimes I get some negative values. Can any one point me my error? Thanks in advance. - First guess: You're a C/C++/Java programmer used to zero-indexing. Matrices in$R$aren't zero-indexed, but rather one-indexed. Also, you use the call V(g)[i-1] which the first time through the loop is V(g)[-1] and the second time is V(g)[0], neither of which, I'm guessing, are what you actually intend to do. – cardinal Apr 18 '11 at 2:30 Also, your call graph.laplacian(g, normalized=TRUE) returns the normalized graph Laplacian. In other words, if$D$is a diagonal matrix of the degrees and$A$is the adjacency matrix, then graph.laplacian(g, normalized=TRUE) returns$I - D^{-1/2} A D^{-1/2}$. You appear to be multiplying on the right and left by$D^{-1/2}$again, which would yield$D^{-1} - D^{-1} A D^{-1}\$. Is that really what you mean to calculate? –  cardinal Apr 18 '11 at 2:33
@cardinal even if I try only the graph.laplacian I get almost the same results. Here the laplacian is D-A, if it is normalized we will have 1 in the diagonal and 1/(sqrt(d[i])*sqrt(d[j]) for the other edges. Here I want to to do D^1/2 * (D-A) * D^1/2 –  sirus Apr 18 '11 at 3:35
Read the documentation carefully. There is a minus sign in front of 1/(sort(d[i])*sqrt(d[j])), from this it is clear that graph.laplacian(g, normalized=TRUE) already returns your desired quantity. You don't need to do any additional construction of Dsqrt or the for-loop, etc. –  cardinal Apr 18 '11 at 4:17
And, somehow, the first sqrt became sort above. Apologies. –  cardinal Apr 18 '11 at 4:42