Tempo de cobertura dos gráficos direcionados

17

Dada uma caminhada aleatória em um gráfico, o tempo de cobertura é a primeira vez (número esperado de etapas) em que todos os vértices são atingidos (cobertos) pela caminhada. Para gráficos não direcionados conectados, o tempo de cobertura é conhecido por ser superior ao . Existem dígrafos fortemente conectados com tempo de cobertura exponencial em n . Um exemplo disto, é o d�rafo consistindo de um ciclo dirigida ( 1 , 2 , . . . , N , 1 ) , e bordos ( j , 1 ) , a partir de vértices j =O(n3)n(1,2,...,n,1)(j,1) . A partir do vértice 1 , o tempo esperado para uma caminhada aleatória atingir o vértice n é Ω ( 2 n ) . Eu tenho duas perguntas :j=2,...,n11nΩ(2n)

1) Quais são as classes conhecidas de gráficos direcionados com tempo de cobertura polinomial? Essas classes podem ser caracterizadas por propriedades teóricas dos grafos (ou) pelas propriedades da matriz de adjacência correspondente (digamos ). Por exemplo, se A é simétrico, o tempo de cobertura do gráfico é polinomial.AA

2) Existem exemplos mais simples (como o exemplo do ciclo mencionado acima) em que o tempo de cobertura é exponencial?

3) Existem exemplos com tempo de cobertura quase polinomial?

Agradeço qualquer indicação de boas pesquisas / livros sobre este tópico.

Shiva Kintali
fonte
2
Seu exemplo de ciclo provavelmente poderia ser generalizado levemente para gráficos com perímetro direcionado com um tempo de cobertura exponencial 2 ential ( n / g ) . g2Ω(n/g)
Derrick Stolee
Além disso, os gráficos do expansor provavelmente têm tempos de cobertura rápidos.
Derrick Stolee
2
O artigo de Mihail descreveu como limitar as taxas de convergência de dígrafos regulares e até cadeias gerais de Markov em termos de condutância. Também pode ser usado para limitar o tempo de cobertura (eu acho). Veja: ieeexplore.ieee.org/iel2/260/2317/00063529.pdf
Zeyu
11
@ Zeyu, deve ser uma resposta!
Suresh Venkat
11
Um artigo de Fan Chung sobre "Laplacianos e a desigualdade de Cheeger para gráficos direcionados" é provavelmente relevante. Ele também tem alguns indicadores para o trabalho anterior de preenchimento. springerlink.com/content/pn149711511373w9
Chandra Chekuri

Respostas:

7

O tempo de mistura claramente polinomial implica tempo de cobertura polinomial. (Bem, não em geral. Precisamos da probabilidade estacionária de pelo menos em cada vértice.) Portanto, verifique o papel de Mihail Condutância e convergência das cadeias de Markov - um tratamento combinatório dos expansores1/poly(n) que comprova a rápida mistura de gráficos direcionados e cadeias gerais de Markov com base na condutância.

Veja também o artigo Pseudoaleatório em digrafos regulares e o problema RL vs. L de Reingold, Trevisan e Vadhan. Seguindo o trabalho de Mihail. Eles definiram o parâmetro que é equivalente a λ 2 ( G ) , o segundo maior autovalor em valor absoluto, quando o gráfico G é reversível no tempo e permanece bem definido para cadeias gerais de Markov. Este parâmetro é depois usado para limitar o tempo de mistura de G .λπ(G)λ2(G)GG

Zeyu
fonte
Para tempos de mistura, há também o trabalho de estrutura relacionado usando a constante de Poinare (que é uma generalização do intervalo espectral para um ajuste irreversível). Laurent Saloff Coste tem algumas notas ( springerlink.com/content/27114435w5149665 ) tratando as cadeias de Markov nessa estrutura. Há também uma monografia ( faculty.uml.edu/rmontenegro/research/TCS008-journal.pdf ) de Tetali e Montenegro. Obviamente, trata-se de tempos de mistura, mas pode ser útil para limitar o tempo de cobertura, como apontado por Zeyu.
Piyush
2

Colin Cooper e Alan Frieze têm um conjunto de resultados no contexto de dígrafos aleatórios que podem ser interessantes. Eles estudam as propriedades de uma caminhada aleatória simples no gráfico direcionado aleatório quando n p = d log n , d > 1 . Eles provaram que:Dn,pnp=dlogn,d>1

  • Para , whp o tempo de cobertura de D n , p é assintótico a d log ( d / ( d - 1 ) ) n log n . Se d = d ( n ) com n , o tempo de cobertura é assimptótica para n log n .d>1Dn,pdlog(d/(d1))nlognd=d(n)nnlogn

  • Se e d > 1 então whp C L n , p ~ d log ( d / ( d - 1 ) ) n log n .p=dlogn/nd>1CGn,pdlog(d/(d1))nlogn

  • Seja e deixe x denotar a solução em ( 0 , 1 ) de x = 1 - e - d x . Seja X g o componente gigante de G n , p , p = d / n . Então whp C X g ~ d x ( 2 - X )d>1x(0,1)x=1edxXgGn,p,p=d/nCXgdx(2x)4(dxlogd)n(logn)2

  • r3Gn,rr[n]r3CGn,rr1r2nlogn

  • m2Gm denotes a preferential attachment graph on average degree 2m then whp CGm2mm1nlogn.

  • If k3 and Gr,k is a random geometric graph in Rk of ball size r such that the expected degree of a vertex is asymptotic to dlogn, then whp CGr,kdlog(dd1)nlogn.

See Cooper, C., & Frieze, A. Stationary distribution and cover time of random walks on random digraphs. Journal of Combinatorial Theory, Series B. (2011).

Juho
fonte