Este modelo de gráficos direcionados aleatórios foi estudado?

O YouTube recentemente adicionou um recurso chamado reprodução automática, onde cada clipe recebe um clipe (presumivelmente relacionado) que o segue. Com efeito, isso define um gráfico direcionado no conjunto de clipes do youtube, em que cada vértice tem um grau 1. O usuário inicia no vértice de sua escolha e faz uma caminhada nesse gráfico.

Isso me fez pensar. Como o gráfico é finito, o usuário ficará preso em um loop. Cada loop atua como um coletor e cada vértice levará o usuário a algum coletor. Isso levanta algumas questões - quantas pias existem? Quantas etapas são necessárias antes que o usuário atinja o loop? Qual é a distribuição dos tamanhos de pia? E assim por diante.

Aqui está um modelo de gráfico aleatório que pode ser usado para modelar esse processo: Para cada vértice $v$ nós escolhemos um único vizinho $w$ uniformemente de forma aleatória e adicione a borda $(v,w)$para o gráfico. Pode ser interessante investigar as propriedades desse modelo e ver se elas podem nos ensinar alguma coisa sobre a rede do Youtube. As pessoas já viram esse tipo de coisa antes?

isso pode ser um pouco inesperado, mas sim, isso foi estudado em pelo menos um contexto específico: PRNGs . um PRNG pode ser visualizado como um gráfico direcionado, especificamente um gráfico funcional (todos os vértices, um único grau) de "valor atual, próximo valor". no entanto, a maioria dos PRNGs é projetada para ter um único ciclo muito longo. existe alguma análise de PRNGs com vários ciclos incorporados. por exemplo:

• Geradores caóticos de números aleatórios com comprimentos de ciclo aleatório / neblina

existe também alguma teoria sobre detecção de ciclo, por exemplo, o algoritmo Tortoise / Hare e Brents. não encontraram outros contextos onde são estudados gráficos funcionais "aleatórios". observe que sua definição não garante que os vértices estejam conectados, não tenho certeza se é isso que você pretendia. haveria alguma teoria sobre quantas arestas teriam que ser colocadas antes que gráficos desconectados separados fossem conectados. Erdos fez estudos nesta área com gráficos não direcionados sobre o modelo Erdos-Renyi e é famoso por ser uma das primeiras descobertas de transições de fase na teoria matemática discreta. os gráficos funcionais aleatórios que você descreve podem ser considerados como uma versão especializada do modelo Erdos Renyi .

É muito fácil dizer algo sobre o comprimento esperado antes de você ficar preso em um loop: se houver $n$ vídeos, ele (a partir de um vídeo aleatório) leva em expectativa $\Theta(\sqrt{n})$ vídeos antes de dar a volta (o valor real é de cerca de $1.25\sqrt{n}$) Este é efetivamente o problema do aniversário, pois cada vez que você desenha um vídeo aleatoriamente.

Como cada vídeo na cadeia de $\Theta(\sqrt{n})$ vídeos é igualmente provável que você faça o loop, a duração média de um loop também é $\Theta(\sqrt{n})$ vídeos (valor real $0.625\sqrt{n}$)

Isso fornece a duração esperada do loop em que você termina depois de iniciar um vídeo aleatório. Isso significa que um loop com muitos vídeos é contado com mais força. Se você deseja saber o tamanho esperado de um loop, se escolher um loop aleatório, isso pode ser encontrado como$T(1)$, Onde

e $T(n)=\frac{n+1}{2}$. Computando os valores de$T$ experimentalmente, parece combinar com $0.625\sqrt{n}$, portanto, as duas formas de contar o comprimento esperado do loop são as mesmas.

Computar o número esperado de ciclos parece ser um problema mais difícil. Começamos contando o número esperado de ciclos de um determinado comprimento. A probabilidade de um nó fazer parte de um ciclo de comprimento 1 é$\frac{1}{n}$, então há expectativa $1$ciclos de comprimento-1. A probabilidade de um nó estar em um ciclo de comprimento 2 é$\frac{n-1}{n}\frac{1}{n}$, então há expectativa $\frac{1}{2}\frac{n-1}{n}$ciclos de comprimento-2. Em geral, o número de ciclos de comprimento$l$ é $\frac{1}{l}\Pi_{i=1}^{l-1} \frac{n-i}{n}$.

Podemos obter um limite superior bruto para o número de ciclos considerando $\Sigma_{i=1}^n \frac{1}{i} = H_n$ qual é $O(\log n)$. Infelizmente, o número de ciclos não parece convergir para$\log n$ então esse limite não é apertado.