I would appreciate help on how to interpret the results of spectral bisectioning of a graph.
Given a $G=(V,E)$ with size $N$ represented by $Q$ its Laplacian matrix where the eigenvalues are ordered as $0=\mu_{N} \leq \mu_{N-1} \leq \ldots \leq \mu_{1}$.
I bisection this graph using the following algorithm:
- Compute the Fiedler eigenvector $x_{N-1}$ corresponding to $\mu_{N-1}$ of $Q$
- for each node $v$ of $G$
- if $x_{N-1}(v)<0$
- put node $v$ in partition $N-$
- else
- put node $v$ in partition $N+$
- if $x_{N-1}(v)<0$
Then I start to randomly remove one link from $G$ and recompute the bisection using the above. I repeat this process $k$ times (i.e., at each step, I remove one more link) and track the resulting partitions each time.
I notice (sometimes) the following happens which I'm unsure how to interpret them:
- When I remove one link, the partition "switch". For example, at $k$, the two partitions may be made up of 15-85 nodes but at $k+1$ (i.e., one new link removed), it suddenly shifts to be 85-15 nodes. Why does the eigenvalues suddenly switch signs?
- When I remove one link, I get no partition i.e., all nodes fall within either $N-$ or $N+$.
- $N+$ or $N-$ is disconnected.
What is the physical interpretations or meanings of the above observations?