Probabilidade de dois vértices serem conectados por algum caminho em um gráfico direcionado aleatório

Defina como um gráfico direcionado aleatoriamente ( vértices; colocamos aresta entre dois vértices com probabilidade ). $G(n, p)$ $n$ $p$

Quais são os resultados conhecidos para o seguinte problema:

Corrija dois vértices e . Qual é a probabilidade de que existe pelo menos um caminho (de comprimento no máximo ) entre e ? (claramente o resultado deve ser uma função de , e ). O limite superior funcionaria também, se não houver resposta exata conhecida. $v$ $u$ $k$ $u$ $v$ $n$ $p$ $k$

graph-theory upper-bounds random-walks random-graphs Daniel
fonte

Quais valores de você está considerando?

p

$p$

Igor Shinkar 29/11

@IgorShinkar faz muita diferença? Eu não tenho um número específico em mente; apenas uma probabilidade .

p \in (0, 1)

$p \in (0,1)$

Daniel

Você tentou modificar a abordagem padrão Erdos-Renyi e, em caso afirmativo, quais são as dificuldades?

usul

Você já pensou em calcular o número esperado de caminhos? Isso deve ser muito mais fácil de calcular / estimar devido à linearidade das expectativas. Seria também um bom proxy para a probabilidade de haver um caminho. ou seja, se o número esperado de caminhos for 0,01, com probabilidade de pelo menos 99%, não haverá caminho. E se o número esperado de caminhos for 100, acho que existe um caminho com alta probabilidade.

Thomas

Boa sugestão Thomas. Apenas para ter certeza de que entendi sua idéia: indique o número do caminho de comprimento

i

$i$ com . O número esperado de caminho de comprimento é (certo?). Defina "X_i = (Y_i> 0)", que mostra o evento de ter um caminho de tamanho entre dois vértices (existência de caminho). Eu sei que , que é delimitado por . Isso daria um limite superior de em .

Y_{i}

$Y_i$

i

$i$

E [Y_{i}] = (\binom{n - 2}{i - 1}) (i - 1)! p^{i}

$E[Y_i] = { n-2 \choose i-1} (i-1)! p^i$

i (i > 0)

$i (i > 0)$

P (X_{i}) = P (Y_{i} > 0) = \sum_{j = 1}^{\infty} P (Y_{i} = j)

$P(X_i) = P(Y_i > 0) = \sum_{j=1}^{\infty} P(Y_i = j)$

E [Y_{i}] = \sum_{j = 0}^{\infty} j . P (Y_{i} = j)

$E[Y_i] = \sum_{j=0}^{\infty} j. P(Y_i = j)$

\sum_{i = 1}^{k} E [Y_{i}]

$\sum_{i=1}^{k}E[Y_i]$

P (\lor_{i = 1}^{k} X_{i} = 1) = P (\lor_{i = 1}^{k} Y_{i} > 0)

$P( \vee_{i=1}^k X_i =1 ) = P( \vee_{i=1}^k Y_i >0)$

Daniel

Respostas:

Considere um processo de exploração de BFS, que prossegue em estágios. Coloque . Dado , explore todas as arestas de a (onde é o conjunto de todos os vértices) e defina para consistir em todos vértices alcançados dessa maneira; seu número tem uma distribuição binomial que pode ser facilmente calculada. Após etapas, verifique se o vértice pertence a . $k$ $V_0 = \{u\}$ $V_0,\ldots,V_i$ $V_i$ $V \setminus \bigcup_{j=0}^i V_j$ $V$ $V_{i+1}$ $k$ $v$ $\bigcup_{j=0}^k V_j$

Observe que esse processo é exatamente o mesmo nos casos não direcionado e direcionado. Portanto, a resposta, seja ela qual for, é idêntica para os dois modelos. Presumivelmente, no caso não direcionado, a resposta é conhecida e pode ser procurada. Caso contrário, você pode tentar estimar estimando os tamanhos $|V_i|$ e assim a probabilidadeque pertence a . $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ $v$ $\bigcup_{i=1}^k V_i$

Yuval Filmus
fonte

Por que o voto negativo?

Yuval Filmus

isso daria uma probabilidade de um caminho de comprimento exatamente k, não no máximo k; isso está correto?

Daniel

Como está escrito, é para a variante "no máximo".

Yuval Filmus