8
$\begingroup$

Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal matrix such that $D_{ii}=deg(i)$ and $D_{ij}=0$ if $i\neq j$. Let $W=D^{-1}A$ be the random walk matrix of $G$.

It's well known that the largest eigenvector (i.e., the eigenvector corresponding to the largest eigenvalue) of $W$ is the probability distribution $\pi$ such that $\pi_i=\frac{deg(i)}{2|E|}$. And there is a simple combinatorial method (in this case, by performing random walk) to approximately computing $\pi$:

  • perform m random walks of length $l$ from some vertex $i$.
  • for each vertex $j$, count the number $w_j$ of walks that ending at $j$.

It can be shown that $\frac{w_k}{m}$ is a good approximation to $\pi_k$ under some mild conditions (for example, if $\pi_k$ is 'large'). One merit of such an algorithm is that we can estimate $\pi$ without traversing the whole graph.

My question is:

Is there a similar combinatorial method for approximately computing the laregest eigenvector of the adjacency matrix $A$, instead of the random walk matrix $W$?

$\endgroup$
  • 1
    $\begingroup$ not to be silly, but $\pi_i = \mathsf{deg}(i)/2|E|$ gives a much simpler combinatorial algorithm to compute $\pi$ $\endgroup$ – Sasho Nikolov Jul 17 '12 at 15:45
  • 1
    $\begingroup$ The value $\pi_i=deg(i)/2|E|$ is tricky, since you will have to tranverse the whole graph to know $|E|$, under the usual assumption that the input is the adjacency matrix or the adjacency list of the graph. In many applications, even such a simple traversal is impossible or at least impractical, for example, to calculate the PageRank value in the huge WWW graph. $\endgroup$ – pepy Jul 18 '12 at 8:29
  • $\begingroup$ that depends on the model, since the $\ell$-hop neighborhood of $i$ can be very large. for web-sized input, you'll need parallelization and then $|E|$ can be computed on map-reduce in a couple of rounds. but maybe your method is less communication-bound $\endgroup$ – Sasho Nikolov Jul 19 '12 at 5:06
  • $\begingroup$ in any case, i'd look into the power method for computing the top eigenvalue of the adjacency. look here for an analysis for a PSD matrix theory.stanford.edu/~trevisan/cs359g/lecture07.pdf $\endgroup$ – Sasho Nikolov Jul 19 '12 at 5:14

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.