@graphty/algorithms / index / indexed / spectralClustering
Function: spectralClustering() ​
spectralClustering(
s,options):SpectralResult
Defined in: indexed/spectral.ts:461
Spectral clustering, the index-based port of the legacy spectralClustering: the k eigenvectors of the graph Laplacian with the smallest eigenvalues embed every node as a point in k dimensions, and k-means splits the points into at most k clusters.
The Laplacian is applied straight from the CSR rows and never built: D - A (unnormalized), I - D^-1/2 A D^-1/2 (normalized, whose embedded rows are then scaled to unit length, as Ng, Jordan and Weiss do) or I - D^-1 A (randomWalk, whose eigenvectors are D^-1/2 times the normalized ones). A node of degree 0 has a zero row. Self-loops are ignored (they cancel in D - A) and a directed snapshot is read as undirected, a reciprocal pair summing. A negative, NaN or infinite weight throws. With k >= nodeCount every node is its own cluster.
The eigenpairs come from subspace iteration with Rayleigh-Ritz, so they are the true smallest ones when converged is true; converged is false when the iteration stopped at its round cap (a small spectral gap, such as a path of hundreds of nodes), and the eigenpairs are then only approximate. The legacy function uses fixed placeholder eigenvalues for k <= 3 and plain power iteration (which finds the LARGEST eigenvectors) above that, and draws its k-means seeds from Math.random unless given a seed. The partitions therefore differ from the legacy function's; one seed gives one result. Labels are dense in first-seen order, so count is below k when k-means leaves a cluster empty.
Parameters ​
s ​
GraphSnapshot
Any snapshot
options ​
k, the Laplacian, the k-means limits, the seed and the weight override
Returns ​
The partition and the eigenpairs it came from