Si tenemos random network/graph con un número de vértices $N_v$ y el número de aristas $N_e$ ¿cómo calculamos la longitud media del camino entre dos vértices aleatorios?
Respuestas
¿Demasiados anuncios?
Este documento 10.1103/PhysRevE.70.056110 calcula analíticamente la longitud característica (= camino más corto medio) $l_{ER}$ de una red aleatoria de Erdös-Renyi con $N$ vértices y $ \langle k \rangle $ grado medio (#edges) $ m= \frac{N \langle k \rangle}{2}$ ).
$$ l_{ER} = \frac{\ln{N} - \gamma}{\ln{\langle k \rangle}} + \frac{1}{2}, $$ o, igualmente $$ l_{ER} = \frac{\ln{N} - \gamma}{\ln(\frac{2m}{N})} + \frac{1}{2}, $$ donde $\gamma \approx 0.57722$ es Constante de Euler .
Misha
Puntos
1723
Podemos hacer algo mejor que la longitud media del camino, porque (para un tamaño suficientemente grande $N_e$ en comparación con $N_v$ ) las longitudes de los caminos entre pares de vértices se concentrarán en uno o dos valores.
Me basaré en el papel El diámetro de los grafos aleatorios por Béla Bollobás. Aunque el diámetro sólo nos indica la longitud del camino más largo del grafo aleatorio, esa longitud de camino será en realidad muy común. Este artículo también trata del grafo aleatorio $\mathcal G_{n,p}$ donde cada arista está presente de forma independiente con probabilidad $p$ pero lo mismo debería ocurrir con el gráfico aleatorio con $n$ vértices y $m = \binom n2p$ bordes aleatorios.
Dejemos que $r = (n-1)p$ (o $r = \frac{2m}{n}$ ) sea el grado medio de este gráfico. Suponemos que $\frac{r}{(\log n)^3} \to \infty$ como $n \to \infty$ . (Para los más pequeños $r$ no tenemos un límite igualmente preciso; además, si $r$ es lo suficientemente pequeño como para que $\frac{r}{\log n} \to 0$ como $n \to \infty$ el gráfico ni siquiera está conectado con alta probabilidad).
Acabará siendo cierto que para algún valor $d = \log_r n + O(1)$ casi todas las distancias en el gráfico son $d-1$ o $d$ . Seré más preciso a continuación.
En primer lugar, hay algunos umbrales críticos en los que el gráfico aleatorio pasa de un diámetro a otro. Supongamos que $p = p(n)$ , $d = d(n)$ son funciones de $n$ con $p \in [0,1], d \in \mathbb N$ y hay una constante $c$ tal que $p^d n^{d-1} = \log \frac{n^2}{c}$ Cuando esto ocurre, tenemos $d \approx \log_r n$ . Entonces, por el lema 5 y el teorema 6 del documento, se cumple lo siguiente con una probabilidad muy alta:
- Para cada vértice $v$ el número de otros vértices a la distancia $d-2$ o menos de $v$ es menor que $2r^{d-2}$ y tenemos $\frac{2r^{d-2}}{n} \to 0$ como $n \to \infty$ . Por lo tanto, una fracción insignificante de los caminos más cortos tiene una longitud $d-2$ o menos.
- Para cada vértice $v$ el número de otras trayectorias a una distancia exacta $d-1$ de $v$ es $(1+o(1))r^{d-1}$ el error relativo pasa a $0$ como $n \to \infty$ . Esta es también una fracción insignificante de las longitudes de las trayectorias.
- Para cada vértice $v$ casi todos los vértices están a una distancia exacta $d$ de $v$ .
- El número total de pares de vértices a distancia $d+1$ entre sí tiene una distribución de Poisson con media $\frac c2$ . (Así que hay muy pocos pares de este tipo y podemos ser muy precisos sobre cuántos).
- No hay pares de vértices a mayor distancia entre sí.
Así que en este rango de $p$ casi todos los caminos más cortos tienen la misma longitud $d$ .
Para una probabilidad de borde general $p$ nos encontramos "entre" dos valores de $d$ . En términos de $n,d$ Supongamos que tenemos $p$ en algún lugar entre $\left(\frac{2\log n}{n^{d-1}}\right)^{1/d}$ y $\left(\frac{2\log n}{n^{d-2}}\right)^{1/(d-1)}$ pero no en el rango cercano a uno de los extremos donde se aplica el caso anterior. Entonces por monotonicidad tenemos, con muy alta probabilidad:
- Aun así, una fracción insignificante de los caminos más cortos desde cualquier vértice $v$ tienen longitud $d-2$ o menos.
- Caminos más cortos de longitud $d-1$ y $d$ existen en una división determinada por el lugar donde nos encontramos en este intervalo; con alta probabilidad, hay muchos de ambos.
- No hay caminos más cortos de longitud $d+1$ o superior.
De forma equivalente, para cualquier $p$ podemos resolver el valor de $d$ donde esto ocurre; obtenemos $d$ sobre $\log_r n$ .
A medida que aumentamos $p$ (o el número de aristas $m$ ) el valor de $d$ se hace cada vez más pequeño. Finalmente, por el Corolario 7 del documento, una vez $m$ satisface $\frac{m^3}{n^2} - \frac12 \log n \to \infty$ el gráfico tiene un diámetro $2$ con alta probabilidad. En este caso, exactamente $m$ de los caminos más cortos tienen longitud $1$ y con alta probabilidad todos los demás tienen longitud $2$ .
