I've been attempting to implement the method of linearized cluster assignments to cluster data just as shown in Linearized Cluster Assignment via Spectral Ordering by Chris Ding and Xiaofeng He. I've read the entire paper but I have some doubts so I'd just like to clear them.
So from what I've understood is that the paper would like to permute, or order, the columns of C, the connectivity matrix, in a way that brings out its cluster structure. In the paper, they use this W similarity matrix to most of their calculations which I'm assuming is the $L_2$ similarity matrix. They go on to find the add some constraints and relaxations which leads them to solving the following eigenvalue equation.
$(D-W)q = {\zeta Dq}$ (where D is a diagonal matrix such that $d_i = \sum_{j=1}^n w_{ij}$)
which they then transform into a more familiar form
$D^{-1/2} W D^{-1/2} = {\lambda} z$
by substituting $D^{-1/2}z = q$
So ${\lambda = 1 - \zeta}$
Now in order to find the permutation to perform on the connectivity matrix C, we must find $q_1$ which I'm assuming to be corresponding to the second smallest ${\zeta}$ and second largest ${\lambda}$ as $q_0$ has been reserved for the smallest ${\zeta}$ and largest ${\lambda}$. The paper then claims that ordering the elements of this $q_1$ in increasing order should give the desired permutation, which should then be performed on C to get the cluster structure. The paper explains how to compute the C on page 5.
So I take it that I find this desired permutation ${\pi}$ by ordering $q_1$, which is the eigenvector of $D^{-1/2} W D^{-1/2}$ corresponding to the second largest ${\lambda}$, in increasing order and finding where the element $i$ in the old $q_1$ maps to after sorting $q_1$, which in this case would map to ${\pi_i}$, then compute C as shown in the paper using the following
$C = D^{1/2} [\sum_{k=1}^K z_kz_k^T]D^{1/2}$ (where $k$ is the number of desried clusters)
and order the column $i$ of the old $C$ to the $\pi_i$ column of the new $C$?
Sorry if any of this is incorrectly formatted or anything. I'm new to Stack Exchange but really needed help with this. Any help is appreciated. Thank you.