6
$\begingroup$

For the sake of discussion, let us say that we have the adjacency matrix $A$ of a graph, on $n$ nodes, from a stochastic block model with 2 blocks. Another name for this (usually used in computer science literature) is a planted partition model. Here is a reference with a formal definition in the 2 block case.

Let us say that we are interested in the behavior of the eignspace corresponding to the 2 leading eigenvectors of $A$ (the ones with the largest and the second most largest eigenvalues in absolute value).

The usual approach to study these eigenvectors is to use perturbation theory (see below), to obtain bounds on the deviation of them from those of say $E[A]$ (the mean of $A$). This does not look sharp to me, as $n \to \infty$ while the average degree stays fixed or grows very slowly, since there is no reason to assume that $A$ concentrates around $E[A]$ in this case.

Are there other ways to get a handle on the eigenvectors without going through perturbation theory? I know this is bit open-ended, but in other words, are there examples where people have shown that the few leading eigenvectors (or a leading eigenspace) of a matrix concentrate sharply while the whole matrix might not?

EDIT: A classical example of what I mean by perturbation theory is Davis-Kahan $\sin(\Theta)$ theorem, with its many variants. Here is another reference. These show that the eigenvectors of a given matrix $A$ are close to a target matrix $M$, with error $\lessapprox \frac1\delta \|A-M\|$ where $\delta$ is the gap in the spectrum of $M$ separating the eigenvalues (corresponding to the desired eigenvectors) from the rest of the spectrum. The difficulty is that these are only useful if $A$ is close to some $M$, say in operator norm, which is a fairly strong condition.

EDIT2: If you want to see an example of application of perturbation theory in action (in almost the same problem as the one I described above) you can take a look at Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model.

$\endgroup$
  • 2
    $\begingroup$ Your question is lacking a lot of information, such as: what is a stochastic blockmodel (with 2, or other number of, blocks)? What is the perturbation theory approach? Providing references would greatly increase the likelihood of your getting an answer. $\endgroup$ – Igor Rivin Sep 22 '13 at 1:10
  • $\begingroup$ OK... thanks. I have added some more references and explanations. $\endgroup$ – passerby51 Sep 22 '13 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.