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.
V(g)[i-1]which the first time through the loop isV(g)[-1]and the second time isV(g)[0], neither of which, I'm guessing, are what you actually intend to do. – cardinal Apr 18 '11 at 2:30graph.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, thengraph.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:33graph.laplacianI get almost the same results. Here the laplacian is D-A, if it is normalized we will have 1 in the diagonal and1/(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:351/(sort(d[i])*sqrt(d[j])), from this it is clear thatgraph.laplacian(g, normalized=TRUE)already returns your desired quantity. You don't need to do any additional construction ofDsqrtor thefor-loop, etc. – cardinal Apr 18 '11 at 4:17sqrtbecamesortabove. Apologies. – cardinal Apr 18 '11 at 4:42