<p>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$.</p>

<p>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 <em>combinatorial method</em> (in this case, by performing random walk) to approximately computing $\pi$:</p>

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

<p>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.</p>

<p>My question is:</p>

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

CC BY-SA 3.0
2012-07-17T15:45:18.870Z
not to be silly, but $\pi_i = \mathsf{deg}(i)/2|E|$ gives a much simpler combinatorial algorithm to compute $\pi$
Sasho Nikolov
CC BY-SA 3.0
2012-07-18T08:29:23.593Z
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.
InfiniteLoops
CC BY-SA 3.0
2012-07-19T05:06:10.330Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-07-19T05:14:28.297Z
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 http://theory.stanford.edu/~trevisan/cs359g/lecture07.pdf
Sasho Nikolov
<ds.algorithms><graph-theory><spectral-graph-theory>
Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph
InfiniteLoops
# Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph

(Asked by: username_0 on 2012-07-17)

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

**Tags:** ds.algorithms, graph-theory, spectral-graph-theory
> **Comments:**
> **username_1**: not to be silly, but $\pi_i = \mathsf{deg}(i)/2|E|$ gives a much simpler combinatorial algorithm to compute $\pi$  
> **username_0**: 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.  
> **username_1**: 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  
> **username_1**: 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 http://theory.stanford.edu/~trevisan/cs359g/lecture07.pdf  

---

## 0 answers

