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$?
