I have a connected weighted graph and I want to use kMeans to cluster the points based on their distance (smaller distances indicate that the nodes are more likely to be in the same cluster).
I computed the Laplacian of the graph and chose the eigenvectors that have corresponding nonzero eigenvalues. I then performed the kMeans in this embedding space represented by the chosen eigenvectors.
In the following example, I want to create 2 clusters and I chose nodes $1$ and $3$ to be the initial centroids. My problem is that the resulting clustering puts nodes $2, 3, 4$ in one cluster and the node $1$ in another one. The desired clustering is $1, 2, 4$ in one cluster and $3$ in the other one.
I am using sklearn.cluster.k-means.