Spectral Clustering Revisited: Information Hidden in the Fiedler Vector
  We are interested in the clustering problem on graphs: it is known that if
there are two underlying clusters, then the signs of the eigenvector
corresponding to the second largest eigenvalue of the adjacency matrix can
reliably reconstruct the two clusters. We argue that the vertices for which the
eigenvector has the largest and the smallest entries, respectively, are
unusually strongly connected to their own cluster and more reliably classified
than the rest. This can be regarded as a discrete version of the Hot Spots
conjecture and should be useful in applications. We give a rigorous proof for
the stochastic block model and several examples.
