<p>Do you know about the following work (and references therein)?  (It's also available on arXiv.)</p>

<p>Bohman, T. and Frieze, A. (2009), Hamilton cycles in 3-out. Random Structures &amp; Algorithms, 35: 393–417. doi: 10.1002/rsa.20272</p>

CC BY-SA 2.5
2010-09-13T19:11:22.830Z
thanks - it's an interesting result, but having a Hamiltonian cycle is far from the type of property I am thinking about.
Lev Reyzin
CC BY-SA 2.5
2010-09-14T15:44:44.177Z
Hm, perhaps I was taking "I am happy with partial results and results about other properties of these graphs" too literally. To me, it seems as if the k-out model is *very close* to the model you are interested in and investigating past results on k-out would be fruitful, especially considering that both Hamiltonicity and rapid mixing can be considered strengthened forms of connectivity in random graph models.
RJK
CC BY-SA 2.5
2010-09-14T16:54:48.917Z
you are right - it is indeed a result about a property of these graphs, and possibly a useful one. I can't give you the accepted answer, but certainly an upvote :)
Lev Reyzin
CC BY-SA 2.5
2010-09-13T16:39:53.120Z
2010-09-13T16:39:53.120Z
RJK
<p>In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$.  I don't remember enough about these proofs to know whether everything goes through in the directed case (certainly some properties are different: the uniform distribution is no longer stationary), but it may be worth looking into.  Good references for expander graphs are <a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf">Expander Graphs and their Applications</a> by Hoory, Linial, and Wigderson and <a href="http://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug10.pdf">Pseudorandomness</a> by Vadhan.</p>

CC BY-SA 2.5
2010-09-14T13:53:19.133Z
Thanks - this is a good reference. I had seen this work before but forgot about it. It's certainly worth going through their proof.
Lev Reyzin
CC BY-SA 2.5
2010-09-13T20:48:27.080Z
2010-09-13T20:48:27.080Z
Ian
<p>I am interested in <strong>properties of random directed graphs with fixed out-degree $d$</strong>.  I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.  </p>

<blockquote>
  <p><strong>Question</strong>: Is anything known about the stationary
  distribution and mixing times of random
  walks on these random graphs (for various
  values of $d$)?  </p>
</blockquote>

<p>I am particularly interested in the case where $d = 2$, which corresponds to a model of random automata over a Boolean alphabet.  (Yes, I realize these graphs are often not connected, but what happens in a given component?)  I am happy with partial results and results about other properties of these graphs.</p>

<p>It seems most of the literature on random graphs focuses on the Erdős–Rényi model, which has very different properties than the model I am thinking about.  </p>

CC BY-SA 2.5
2010-09-13T15:30:06.203Z
I can offer this: if you search on the phrase "clustering coefficient" you might find more literature that relates.  I decided I was interested in other things, so I don't remember specifics.
Aaron Sterling
CC BY-SA 2.5
2010-09-13T16:04:31.167Z
you should hunt for models of web graphs (start with the Aiello/Chung paper (http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/999188420) and work forward). It's possible you'll find interesting models of web graphs. Also look at Christos Faloutsos' recent work
Suresh Venkat
CC BY-SA 2.5
2010-09-13T17:32:49.513Z
thanks for the pointer - I've looked at Chung's work and this paper - while they do consider interesting models, they unfortunately don't consider mine...
Lev Reyzin
CC BY-SA 2.5
2010-09-13T20:14:42.293Z
You suggest that the process occurs with replacement.  Does this mean that you allow multidigraphs (with possibly multiple arcs from s to t)?
András Salamon
CC BY-SA 2.5
2010-09-13T20:25:58.023Z
That's right - in the random walk you take each edge equiprobably, and with multiple arcs, you increase the probability of a given transition (and we allow self loops too).  However, if you wish to answer the question for choosing edges without replacement, that's fine too.
Lev Reyzin
CC BY-SA 2.5
2010-09-16T15:28:09.733Z
@Lev: Your graph model can be seen as the sum of d independently chosen random graphs where each vertex chooses a next neighbour uniformly at random.  This would seem to make analysis easier?
András Salamon
CC BY-SA 2.5
2010-09-16T21:22:40.263Z
@András I'm afraid not -- at least I can't see how it would help. For example in the undirected case, for d=3, it is a sum of 3 d=1 random graphs. But for d=1 you get no or polynomially slow mixing, whereas for d=3 you get an expander!
Lev Reyzin
CC BY-SA 2.5
2010-09-17T09:40:42.847Z
@Lev: Ah, right.  Never mind!
András Salamon
<graph-theory><co.combinatorics><automata-theory><random-walks>
Properties of Random Directed Graphs with Fixed Out-Degree
Lev Reyzin
# Properties of Random Directed Graphs with Fixed Out-Degree

(Asked by: username_0 on 2010-09-13)

I am interested in **properties of random directed graphs with fixed out-degree $d$**. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.

> **Question**: Is anything known about the stationary
> distribution and mixing times of random
> walks on these random graphs (for various
> values of $d$)?

I am particularly interested in the case where $d = 2$, which corresponds to a model of random automata over a Boolean alphabet. (Yes, I realize these graphs are often not connected, but what happens in a given component?) I am happy with partial results and results about other properties of these graphs.

It seems most of the literature on random graphs focuses on the Erdős–Rényi model, which has very different properties than the model I am thinking about.

**Tags:** graph-theory, co.combinatorics, automata-theory, random-walks

> **Comments:**
> **username_1**: I can offer this: if you search on the phrase "clustering coefficient" you might find more literature that relates.  I decided I was interested in other things, so I don't remember specifics.  
> **username_2**: you should hunt for models of web graphs (start with the Aiello/Chung paper (http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/999188420) and work forward). It's possible you'll find interesting models of web graphs. Also look at Christos Faloutsos' recent work  
> **username_0**: thanks for the pointer - I've looked at Chung's work and this paper - while they do consider interesting models, they unfortunately don't consider mine...  
> **username_3**: You suggest that the process occurs with replacement.  Does this mean that you allow multidigraphs (with possibly multiple arcs from s to t)?  
> **username_0**: That's right - in the random walk you take each edge equiprobably, and with multiple arcs, you increase the probability of a given transition (and we allow self loops too).  However, if you wish to answer the question for choosing edges without replacement, that's fine too.  
> **username_3**: @Lev: Your graph model can be seen as the sum of d independently chosen random graphs where each vertex chooses a next neighbour uniformly at random.  This would seem to make analysis easier?  
> **username_0**: @András I'm afraid not -- at least I can't see how it would help. For example in the undirected case, for d=3, it is a sum of 3 d=1 random graphs. But for d=1 you get no or polynomially slow mixing, whereas for d=3 you get an expander!  
> **username_3**: @Lev: Ah, right.  Never mind!  

---

## 2 answers

### Answer by username_5 on 2010-09-13. Score: 10 | Accepted answer

In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$. I don't remember enough about these proofs to know whether everything goes through in the directed case (certainly some properties are different: the uniform distribution is no longer stationary), but it may be worth looking into. Good references for expander graphs are [Expander Graphs and their Applications](http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) by Hoory, Linial, and Wigderson and [Pseudorandomness](http://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug10.pdf) by Vadhan.

> **Comments:**
> **username_0**: Thanks - this is a good reference. I had seen this work before but forgot about it. It's certainly worth going through their proof.  

---

### Answer by username_4 on 2010-09-13. Score: 7

Do you know about the following work (and references therein)? (It's also available on arXiv.)

Bohman, T. and Frieze, A. (2009), Hamilton cycles in 3-out. Random Structures & Algorithms, 35: 393–417. doi: 10.1002/rsa.20272

> **Comments:**
> **username_0**: thanks - it's an interesting result, but having a Hamiltonian cycle is far from the type of property I am thinking about.  
> **username_4**: Hm, perhaps I was taking "I am happy with partial results and results about other properties of these graphs" too literally. To me, it seems as if the k-out model is *very close* to the model you are interested in and investigating past results on k-out would be fruitful, especially considering that both Hamiltonicity and rapid mixing can be considered strengthened forms of connectivity in random graph models.  
> **username_0**: you are right - it is indeed a result about a property of these graphs, and possibly a useful one. I can't give you the accepted answer, but certainly an upvote :)  

---

