<p>Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to directed graphs. </p>

<p>I state a possible generalization of Cheeger's inequality next. I am asking first about its correctness and secondly about whether any results along these lines are known or possible. </p>

<p>Let $G=(V,E)$ be a strongly connected directed graph. Consider the lazy random walk on $G$: this is the Markov chain whose transition probability matrix is $P_{ii} = 1/2$, $P_{ij}=1/d(i)$ if $(i,j) \in E$, where $d(i)$ is the out-degree of node $i$, and $P_{ij}=0$ otherwise. </p>

<p>Let $\pi$ be the unique left eigenvector corresponding to the eigenvalue $1$. Naturally, define $\pi(S) = \sum_{i \in S} \pi(i)$. Then the Cheeger constant of $P$ may be defined as  $$ h(P) = \min_{S \subset V} \frac{\sum_{i \in S, j \in S^c} \pi(i) P_{ij}}{\pi(S) \pi(S^c)}$$</p>

<p>Now if $G$ is <em>undirected</em>, the part of Cheeger's inequality I am interested in says that
$$ 1 - \lambda_1 \geq \Omega(h(P)^2)$$ where $\lambda_1$ is the largest eigenvalue of $P$ not equal to $1$. </p>

<p>In the directed case, the eigenvalues are no longer real. Nevertheless, one can define $\lambda$ to be the largest absolute value of any eigenvalue of $P$ not equal to $1$. Then, is it true that </p>

<p>$$ 1 - \lambda \geq \Omega (h(P)^2)$$ 
Alternatively, is any sort of result along these lines possible, perhaps with different definition of Cheeger constant? </p>

<p>The only reference I was able to find was <a href="http://people.cs.umass.edu/~mahadeva/cs791bb/reading/dichee.pdf">Laplacians and the Cheeger inequality
for directed graphs</a>, F. Chung, Annals of Combinatorics, 2005 (see also <a href="http://www.math.ucsd.edu/~fan/teach/262/notes/paul/11_16_notes.pdf">these lecture notes</a>). However, the main results of that paper appear to be different than what I'm asking about. In particular, this paper seems to prove a form of Cheeger's inequality for a certain symmetric matrix, though the symmetric matrix is derived from a directed graph.</p>

CC BY-SA 3.0
2012-07-21T17:46:31.670Z
That's an interesting way to generalize Cheeger. My feeling is that it will help to first look at the irreducible aperiodic case, so that you have a unique maximum (in absolute value) real simple eigenvalue, and corresponding eigenvector is real and positive (by Perron-Frobenius).
Sasho Nikolov
CC BY-SA 3.0
2012-07-21T17:57:43.760Z
I believe I am looking at that case: (i) irreducible - $G$ is assumed to be strongly connected (ii) aperiodic - $P$ is defined to have $P_{ii} \geq 1/2$; this was precisely so as not to deal with periodicity issues.
robinson
CC BY-SA 3.0
2012-07-21T18:03:46.383Z
I missed the strongly connected part. Cool.
Sasho Nikolov
CC BY-SA 3.0
2015-03-11T13:01:02.993Z
Have you elaborated on your ideas? I would be very interested to hear about further developments.
Delio M.
<graph-theory><co.combinatorics><pr.probability><markov-chains><random-walks>
Cheeger's inequality for directed graphs?
robinson
# Cheeger's inequality for directed graphs?

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

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to directed graphs.

I state a possible generalization of Cheeger's inequality next. I am asking first about its correctness and secondly about whether any results along these lines are known or possible.

Let $G=(V,E)$ be a strongly connected directed graph. Consider the lazy random walk on $G$: this is the Markov chain whose transition probability matrix is $P\_{ii} = 1/2$, $P\_{ij}=1/d(i)$ if $(i,j) \in E$, where $d(i)$ is the out-degree of node $i$, and $P\_{ij}=0$ otherwise.

Let $\pi$ be the unique left eigenvector corresponding to the eigenvalue $1$. Naturally, define $\pi(S) = \sum\_{i \in S} \pi(i)$. Then the Cheeger constant of $P$ may be defined as $$ h(P) = \min\_{S \subset V} \frac{\sum\_{i \in S, j \in S^c} \pi(i) P\_{ij}}{\pi(S) \pi(S^c)}$$

Now if $G$ is *undirected*, the part of Cheeger's inequality I am interested in says that
$$ 1 - \lambda\_1 \geq \Omega(h(P)^2)$$ where $\lambda\_1$ is the largest eigenvalue of $P$ not equal to $1$.

In the directed case, the eigenvalues are no longer real. Nevertheless, one can define $\lambda$ to be the largest absolute value of any eigenvalue of $P$ not equal to $1$. Then, is it true that

$$ 1 - \lambda \geq \Omega (h(P)^2)$$
Alternatively, is any sort of result along these lines possible, perhaps with different definition of Cheeger constant?

The only reference I was able to find was [Laplacians and the Cheeger inequality
for directed graphs](http://people.cs.umass.edu/~mahadeva/cs791bb/reading/dichee.pdf), F. Chung, Annals of Combinatorics, 2005 (see also [these lecture notes](http://www.math.ucsd.edu/~fan/teach/262/notes/paul/11_16_notes.pdf)). However, the main results of that paper appear to be different than what I'm asking about. In particular, this paper seems to prove a form of Cheeger's inequality for a certain symmetric matrix, though the symmetric matrix is derived from a directed graph.

**Tags:** graph-theory, co.combinatorics, pr.probability, markov-chains, random-walks
> **Comments:**
> **username_1**: That's an interesting way to generalize Cheeger. My feeling is that it will help to first look at the irreducible aperiodic case, so that you have a unique maximum (in absolute value) real simple eigenvalue, and corresponding eigenvector is real and positive (by Perron-Frobenius).  
> **username_0**: I believe I am looking at that case: (i) irreducible - $G$ is assumed to be strongly connected (ii) aperiodic - $P$ is defined to have $P_{ii} \geq 1/2$; this was precisely so as not to deal with periodicity issues.  
> **username_1**: I missed the strongly connected part. Cool.  
> **username_2**: Have you elaborated on your ideas? I would be very interested to hear about further developments.  

---

## 0 answers

