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.

$\endgroup$
  • $\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 Sep 13 '10 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 Sep 13 '10 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 Sep 13 '10 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 Sep 13 '10 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 Sep 13 '10 at 20:25
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.

$\endgroup$
  • $\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 Sep 14 '10 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

$\endgroup$
  • $\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 Sep 13 '10 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 Sep 14 '10 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 Sep 14 '10 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.

$\endgroup$
  • 1
    $\begingroup$ do you have a link for it ? $\endgroup$ – Suresh Venkat Jan 5 '11 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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