Propiedades de los gráficos dirigidos al azar con grado de salida fijo

Estoy interesado en las propiedades de los gráficos dirigidos al azar con un grado externo fijo $d$ . Me estoy imaginando un modelo de gráfico aleatorio donde cada vértice elige d vecinos (digamos, con reemplazo) uar

Pregunta : ¿Se sabe algo sobre la distribución estacionaria y los tiempos de mezcla de caminatas aleatorias en estos gráficos aleatorios (para varios valores de )? $d$

Estoy particularmente interesado en el caso donde , que corresponde a un modelo de autómatas aleatorios sobre un alfabeto booleano. (Sí, me doy cuenta de que estos gráficos a menudo no están conectados, pero ¿qué sucede en un componente dado?) Estoy satisfecho con los resultados parciales y los resultados sobre otras propiedades de estos gráficos. $d = 2$

Parece que la mayor parte de la literatura sobre gráficos aleatorios se centra en el modelo Erdős-Rényi, que tiene propiedades muy diferentes al modelo en el que estoy pensando.

graph-theory co.combinatorics automata-theory random-walks Lev Reyzin
fuente

Puedo ofrecer esto: si busca en la frase "coeficiente de agrupamiento", puede encontrar más literatura relacionada. Decidí que estaba interesado en otras cosas, así que no recuerdo detalles.

Aaron Sterling el

debe buscar modelos de gráficos web (comience con el documento de Aiello / Chung ( projecteuclid.org/… ) y continúe). Es posible que encuentre modelos interesantes de gráficos web. Mire también el trabajo reciente de Christos Faloutsos

Suresh Venkat

gracias por el puntero - He visto el trabajo de Chung y este artículo - aunque consideran modelos interesantes, desafortunadamente no consideran el mío ...

Lev Reyzin

Sugieres que el proceso ocurra con el reemplazo. ¿Significa esto que permite multidigraphs (con posiblemente múltiples arcos de s a t)?

András Salamon

Así es: en la caminata aleatoria, tomas cada borde de manera equiparable, y con múltiples arcos, aumentas la probabilidad de una transición dada (y también permitimos bucles automáticos). Sin embargo, si desea responder la pregunta para elegir bordes sin reemplazo, también está bien.

Lev Reyzin

Respuestas:

En el caso no dirigido, los gráficos aleatorios regulares son expansores con alta probabilidad (no para , pero creo que suficiente), lo que implica que el tiempo de mezcla de caminatas aleatorias es . No recuerdo lo suficiente sobre estas pruebas para saber si todo pasa en el caso dirigido (ciertamente algunas propiedades son diferentes: la distribución uniforme ya no es estacionaria), pero puede valer la pena analizarla. Buenas referencias para los gráficos de expansión son Expander Gráficos y sus aplicaciones por Hoory, Linial, y Wigderson y pseudoaleatoriedad por Vadhan. $d$ $d=2$ $d \ge 3$ $O(\log n)$

Ian
fuente

Gracias, esta es una buena referencia. Había visto este trabajo antes pero lo olvidé. Ciertamente vale la pena pasar por su prueba.

Lev Reyzin

¿Conoces el siguiente trabajo (y referencias allí)? (También está disponible en arXiv).

Bohman, T. y Frieze, A. (2009), Hamilton realiza ciclos de 3 salidas. Estructuras aleatorias y algoritmos, 35: 393–417. doi: 10.1002 / rsa.20272

RJK
fuente

gracias, es un resultado interesante, pero tener un ciclo hamiltoniano está lejos del tipo de propiedad en la que estoy pensando.

Lev Reyzin

Hm, tal vez estaba tomando "Estoy contento con resultados parciales y resultados sobre otras propiedades de estos gráficos" demasiado literalmente. Para mí, parece que el modelo k-out está muy cerca del modelo que le interesa e investigar resultados anteriores sobre k-out sería fructífero, especialmente teniendo en cuenta que tanto Hamiltonicity como la mezcla rápida pueden considerarse formas fortalecidas de conectividad en Modelos de gráficos aleatorios.

RJK

tiene razón: de hecho, es el resultado de una propiedad de estos gráficos, y posiblemente una útil. No puedo darle la respuesta aceptada, pero sin duda un

voto a favor

¿Sigues investigando el problema? Este artículo es en realidad un poco relevante: Alan Frieze, Páll Melsted y Michael Mitzenmacher, " Un análisis de Random-Walk Cuckoo Hashing ", 2009.

Kaveh
fuente

Tienes un enlace para eso ?

Suresh Venkat