17
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Commented Sep 13, 2010 at 15:30
  • $\begingroup$ 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 $\endgroup$
    – Suresh Venkat
    Commented Sep 13, 2010 at 16:04
  • $\begingroup$ 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... $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 13, 2010 at 17:32
  • $\begingroup$ You suggest that the process occurs with replacement. Does this mean that you allow multidigraphs (with possibly multiple arcs from s to t)? $\endgroup$
    – András Salamon
    Commented Sep 13, 2010 at 20:14
  • $\begingroup$ 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. $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 13, 2010 at 20:25

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks - this is a good reference. I had seen this work before but forgot about it. It's certainly worth going through their proof. $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 14, 2010 at 13:53
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks - it's an interesting result, but having a Hamiltonian cycle is far from the type of property I am thinking about. $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 13, 2010 at 19:11
  • $\begingroup$ 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. $\endgroup$
    – RJK
    Commented Sep 14, 2010 at 15:44
  • $\begingroup$ 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 :) $\endgroup$
    – Lev Reyzin ♦
    Commented Sep 14, 2010 at 16:54
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ do you have a link for it ? $\endgroup$
    – Suresh Venkat
    Commented Jan 5, 2011 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.