# Properties of Random Directed Graphs with Fixed Out-Degree

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.

• 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. Sep 13 '10 at 15:30
• you should hunt for models of web graphs (start with the Aiello/Chung paper (projecteuclid.org/…) and work forward). It's possible you'll find interesting models of web graphs. Also look at Christos Faloutsos' recent work Sep 13 '10 at 16:04
• 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... Sep 13 '10 at 17:32
• You suggest that the process occurs with replacement. Does this mean that you allow multidigraphs (with possibly multiple arcs from s to t)? Sep 13 '10 at 20:14
• 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. Sep 13 '10 at 20:25

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 by Hoory, Linial, and Wigderson and Pseudorandomness by Vadhan.

• Thanks - this is a good reference. I had seen this work before but forgot about it. It's certainly worth going through their proof. Sep 14 '10 at 13:53

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

• thanks - it's an interesting result, but having a Hamiltonian cycle is far from the type of property I am thinking about. Sep 13 '10 at 19:11
• 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
Sep 14 '10 at 15:44
• 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 :) Sep 14 '10 at 16:54

Are you still looking into the problem? This paper is actually a bit relevant: Alan Frieze, Páll Melsted and Michael Mitzenmacher, "An Analysis of Random-Walk Cuckoo Hashing", 2009.

• do you have a link for it ? Jan 5 '11 at 0:51