Propriedades de gráficos direcionados aleatórios com grau externo fixo

17

Estou interessado em propriedades de gráficos direcionados aleatórios com grau externo fixod . Estou imaginando um modelo de gráfico aleatório em que cada vértice escolhe d vizinhos (digamos, com substituição) uar

Pergunta : Sabe-se alguma coisa sobre a distribuição estacionária e os tempos de mistura de passeios aleatórios nesses gráficos aleatórios (para vários valores de )? d

Estou particularmente interessado no caso em que , que corresponde a um modelo de autômato aleatório sobre um alfabeto booleano. (Sim, percebo que esses gráficos geralmente não estão conectados, mas o que acontece em um determinado componente?) Estou feliz com resultados parciais e com outras propriedades desses gráficos.d=2

Parece que a maior parte da literatura sobre gráficos aleatórios se concentra no modelo Erdős – Rényi, que possui propriedades muito diferentes do modelo em que estou pensando.

Lev Reyzin
fonte
Posso oferecer o seguinte: se você pesquisar a frase "coeficiente de agrupamento", poderá encontrar mais literatura relacionada. Decidi que estava interessado em outras coisas, então não me lembro de detalhes.
Aaron Sterling
você deve procurar modelos de gráficos da web (comece com o artigo Aiello / Chung ( projecteuclid.org/… ) e prossiga). É possível que você encontre modelos interessantes de gráficos da web. Veja também o trabalho recente de Christos Faloutsos
Suresh Venkat
agradecimentos para o ponteiro - Eu olhei para o trabalho de Chung e este papel - enquanto eles consideram modelos interessantes, eles infelizmente não consideram meu ...
Lev Reyzin
Você sugere que o processo ocorra com a substituição. Isso significa que você permite multidígrafos (com possivelmente vários arcos de s a t)?
András Salamon
Isso mesmo - na caminhada aleatória, você escolhe cada extremidade de forma equitativa e, com vários arcos, aumenta a probabilidade de uma determinada transição (e também permitimos auto-loops). No entanto, se você deseja responder à pergunta sobre a escolha de arestas sem substituição, tudo bem.
Lev Reyzin

Respostas:

10

No caso não direcionado, os gráficos regulares aleatórios são expansores com alta probabilidade (não para d = 2 , mas acho que d 3 é suficiente), o que implica que o tempo de mistura dos passeios aleatórios é O ( log n ) . Não me lembro o suficiente dessas provas para saber se tudo passa no caso direcionado (certamente algumas propriedades são diferentes: a distribuição uniforme não é mais estacionária), mas pode valer a pena investigar. Boas referências para gráficos expansores são Expander Graphs e suas aplicações de Hoory, Linial e Wigderson e Pseudorandomness de Vadhan.dd=2d3O(registron)

Ian
fonte
Obrigado - esta é uma boa referência. Eu já tinha visto esse trabalho antes, mas esqueci. Certamente vale a pena passar pela prova deles.
Lev Reyzin
7

Você conhece o seguinte trabalho (e suas referências)? (Também está disponível no arXiv.)

Bohman, T. e Frieze, A. (2009), Hamilton pedalam em três saídas. Random Structures & Algorithms, 35: 393–417. doi: 10.1002 / rsa.20272

RJK
fonte
obrigado - é um resultado interessante, mas ter um ciclo hamiltoniano está longe do tipo de propriedade em que estou pensando.
Lev Reyzin
Hm, talvez eu estivesse dizendo "Estou feliz com resultados parciais e com outras propriedades desses gráficos" muito literalmente. Para mim, parece que o modelo k-out está muito próximo do modelo em que você está interessado e investigar os resultados passados ​​no k-out seria proveitoso, especialmente considerando que Hamiltonicidade e mistura rápida podem ser consideradas formas fortalecidas de conectividade no modelos de gráficos aleatórios.
RJK
você está certo - é realmente um resultado sobre uma propriedade desses gráficos e possivelmente uma útil. Eu não posso dar-lhe a resposta aceita, mas, certamente, um upvote :)
Lev Reyzin
2

Você ainda está investigando o problema? Este artigo é realmente um pouco relevante: Alan Frieze, Páll Melsted e Michael Mitzenmacher, " An Analysis of Random-Walk Cuckoo Hashing ", 2009.

Kaveh
fonte
11
você tem um link para isso?
quer tocar hoje