1
$\begingroup$

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:

  1. Compute the Fiedler eigenvector $x_{N-1}$ corresponding to $\mu_{N-1}$ of $Q$
  2. 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+$

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:

  1. 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?
  2. When I remove one link, I get no partition i.e., all nodes fall within either $N-$ or $N+$.
  3. $N+$ or $N-$ is disconnected.

What is the physical interpretations or meanings of the above observations?

$\endgroup$
6
  • 1
    $\begingroup$ 1. If $x=x_{N-1}$ is an eigenvalue so is $-x$ so the partition should be an unordered pair $\{{N-,N+\}}$. 2. This seems to indicate that you are finding an eigenvector for the largest eigenvalue of the current graph. Can you give an example? 3. Do you check if the graph stays connected with the deleted links? Again an example might be nice. $\endgroup$ Jul 13, 2015 at 20:00
  • $\begingroup$ 2). may imply that your graph got disconnected after the last removal, and your $\mu_{N-1}=0$. Then the eigenvector you find may be positive on one of resulting 'halves' and 0 on the other, giving you the "no partition" situation according to your algorithm. $\endgroup$ Jul 13, 2015 at 20:14
  • $\begingroup$ @ Aaron Meyerowitz Thank you for your response. $x_{N-1}$ is the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix (a.k.a algebraic connectivity). Also, in my program, I do not stop even when the graph got disconnected (I'm curious to find out the behaviour of this Fiedler's spectral bipartitioning technique). $\endgroup$
    – Val K
    Jul 13, 2015 at 21:30
  • $\begingroup$ @ Piyush Thanks. First, I put all non-negative (i.e., including zero) eigenvector components to $N+$. But your point being the graph got disconnected seems good. Indeed, after a few tests, observation (2) usually happens when the graph first get disconnected, resulting in all Fiedler eigenvector components to be +ve. If I continue the iteration, the sets $N+$ and $N-$ again becomes populated (i.e., I get again 2 partitions). This I guess is due to the appearance of multiple disconnected graph components. Hm, I am still unsure how to interpret the observations. $\endgroup$
    – Val K
    Jul 13, 2015 at 22:04
  • 1
    $\begingroup$ Also see answer in this thread:mathoverflow.net/questions/120336/… $\endgroup$ Jul 14, 2015 at 18:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.