Breve análisis de la robustez de la Web

Para estrenar en condiciones el plugin de ecuaciones de Latex para WordPress, podía haber elaborado una entrada sobre la probabilidad de que El Canto del Moco se disolviera y no volviera nunca a la música, pero corría el riesgo de que saliera cercana a cero y no quería llevarme ese disgusto.

Así que usaremos las ecuaciones para algo más interesante.

Hablemos, un poner, de la Web.

Matemáticamente, la web se puede considerar como un grafo en el que los nodos son las páginas web y los arcos los enlaces entre ellas. En ese sentido, el estudio de su topología global (patrón de conexionado) puede dar lugar a conclusiones interesantes.

Modelos de la topología de la Web

En 1999, Albert-László Barabási y Réka Albert mostraron empíricamente que la Web (entre otras) es una red con una topología compleja, llamada red libre de escala. Este tipo de topologías se producen, según los autores, porque se añaden nodos (páginas) constantemente y porque las nuevas páginas se suelen enlazar más probablemente con otras que ya están bastante conectadas que con páginas poco conocidas. En concreto, en las redes libres de escala, la probabilidad de que un nodo esté conectado con otros k nodos es de la forma P_{libre}(k)\propto{k^{-\lambda}}, siendo para la Web \lambda\simeq2.1\pm0.1. Eso significa que la probabilidad es muy pequeña para nodos muy conectados y más grande para nodos (páginas) con pocos enlaces. Más formalmente, como P_{libre}(k) debe ser una probabilidad, tiene que cumplirse que \forall{k}:P_{libre}(k)\in[0..1] y que \sum_{k=1}^{A}P_{libre}(k)=1, donde A sería N(N-1), siendo N el número de nodos del grafo, o de páginas de la Web, que en Diciembre de 2008 era de unos 186 millones.

En resumidas cuentas, para la web podemos considerar P_{libre}(k)=ck^{-\lambda}, donde c=\frac{1}{\sum_{k=1}^{A}{k^{-\lambda}}}.

El que la probabilidad de tener una serie de enlaces con otras páginas cumpla esta ecuación (que llamaremos a partir de ahora modelo libre de escala) hace que la Web tenga una estructura muy particular: como ya hemos comentado, hay unos pocos nodos (pocos porque la probabilidad de que los haya es escasa), que se llaman concentradores, con muchísimas conexiones con otros. El resto (como este blog) tienen escasas conexiones. Ejemplos claros de concentradores en la Web son Google, blogs muy citados (como Microsiervos), etc.

Podríamos usar otros modelos. Supongamos que la Web no tuviera estructura, que fuera mucho más uniforme. El modelo más sencillo viene de considerar que la probabilidad de que una página dada tenga k\geq1 enlaces con otras sea una constante P_{uniforme}(k)=\rho. Asumiremos que \rho está definido de tal forma que P_{uniforme}(k) es una probabilidad, es decir, \sum_{k=1}^{A}\rho=A\rho=1\Rightarrow\rho=\frac{1}{A}\in[0..1]. Llamaremos a éste, modelo uniforme.

Robustez de la Web

La robustez de la Web podría medirse como el número esperado de enlaces que dejan de funcionar cuando se cae una página, al que llamaremos de manera general \varepsilon. En el caso de la red libre de escala, este número de enlaces es igual, por nuestra definición, a la esperanza matemática \varepsilon_{libre}=E[P_{libre}(k)]=\sum_{k=1}^{A}{kck^{-\lambda}}. En el caso de la red uniforme, tendremos \varepsilon_{uniforme}=\sum_{k=1}^{A}{k\rho}.

Cuanto menor sea \varepsilon mejor, por supuesto: siempre que haya una probabilidad parecida de que se caiga una página cualquiera, el número de enlaces afectados sería menor. Hay que tener en cuenta que éste es un análisis un poco pesimista, porque los concentradores, en el mundo real, suelen estar más protegidos ante caídas que las páginas del común de los mortales. Por tanto los resultados que pondremos a continuación serían incluso mejorados por la Web real.

Robustez del modelo uniforme

Calcular la robustez en una red uniforme, o sea, el valor de \varepsilon_{uniforme}, es sencillo, puesto que aparece una progresión aritmética al resolverlo: \varepsilon_{unifome}=\sum_{k=1}^{A}{k\rho}=\rho\sum_{k=1}^{A}k=\rho\frac{A(A+1)}{2}=\frac{A+1}{2}, es decir, el número de enlaces caídos sería aproximadamente la mitad del número máximo de enlaces que podría existir para cualquier página, lo cual tiene su lógica dada la uniformidad del modelo. Este número sin embargo sería enorme para la Web: significaría que de media, cualquier caída de página no sería mucho menos catastrófica que la caída de un concentrador de una red libre de escala…

Robustez del modelo libre de escala

Calcular el valor de \varepsilon_{libre} es bastante más complicado. Los sumatorios involucrados cuando se desarrolla: \varepsilon_{libre}=\sum_{k=1}^{A}{kck^{-\lambda}}=c\sum_{k=1}^{A}{k^{1-\lambda}}=\frac{\sum_{k=1}^{A}{k^{1-\lambda}}}{\sum_{k=1}^{A}{k^{-\lambda}}}=\frac{\alpha(\lambda,A)}{\beta(\lambda,A)} no tienen expresión cerrada, incluso a pesar de ser sumas finitas. Pero podemos acotar un intervalo de valores en el que se encuentre \varepsilon_{libre}.Para encontrar ese intervalo nos hace falta encontrar a su vez intervalos en los que se encuentren \alpha(\lambda,A) y \beta(\lambda,A).

Se puede ver que los sumatorios de la forma \sum_{k=1}^{A}{k^{-x}} son monotónicamente crecientes respecto a A, ya que todos los términos de la suma son estrictamente positivos y además tenemos que x\geq1. Por tanto, el mínimo de ese sumatorio sería 1 (para cuando A=1), independientemente del valor de \lambda, que no podría disminuir esa cota. Los intervalos que encierran a \alpha(\lambda,A) y \beta(\lambda,A) comienzan, pues, en 1.

Los extremos máximos de esos intervalos para un valor dado de \lambda estarían acotados por los valores de los respectivos sumatorios cuando A\rightarrow\infty. Curiosamente, la función Zeta de Riemann, para argumentos reales, se define precisamente como \zeta(x)=\sum_{k=1}^{\infty}{k^{-x}}. Existen algunos valores exactos calculados para la función Zeta, y el resto pueden aproximarse numéricamente (la función Zeta es monótona decreciente para valores de su argumento mayores que 1). Si encontramos el valor de la función Zeta para cada \lambda posible y tomamos el mayor de ellos, podremos tener una cota superior para los intervalos de \alpha(\lambda,A) y \beta(\lambda,A).

Habíamos dicho que Barabási y Albert habían estimado \lambda\simeq2.1\pm0.1 para la Web. Como la función Zeta es monótona decreciente para su argumento, el valor máximo de \alpha(\lambda,A) con respecto a esos valores de \lambda vendría dado para el \lambda más pequeño (sumarle 1 como en el exponente de la función \alpha no cambia su característica decreciente). Lamentablemente, con \lambda=2, que es el valor mínimo de \lambda para la Web, tenemos  \zeta(-(1-\lambda))=\zeta(1)=\infty, es decir, que la función Zeta no nos sirve de ayuda. Tenemos que buscar una cota de otra forma. Podemos estimarla numéricamente, por ejemplo para A=200.000.000(200.000.000-1), que sería superior a la Web en Diciembre de 2008, y suponer que es el tamaño máximo que tiene ésta. Tendremos entonces como cota superior max(\alpha(2,A))\simeq38 (ese sumatorio crece muy lentamente cuando A crece, así que debería cambiar muy poco en el futuro conforme la Web se expanda).

Por otro lado, en el caso de \beta(\lambda,A) sí hay cota estimable mediante la función Zeta: lim_{A\rightarrow\infty}{\beta(2.0,A)}=\zeta(2.0)=\frac{\pi^2}{6}=1.6449..

En definitiva, para la Web: \alpha(\lambda,A)\in[1,38] y \beta(\lambda,a)\in[1,1.6449]. Eso hace que \varepsilon_{libre}\in[\frac{1}{1.6449},38]. Podemos hacer una estimación más exacta si emparejamos los valores de \alpha(\lambda,A) y \beta(\lambda,A) según los valores de \lambda, aunque no superaremos el peor caso por la monotonicidad decreciente de la función Zeta. En particular, para los valores \lambda\in\{2.0,2.1,2.2\} tendremos \varepsilon_{libre}\in\{38,10.5844,5.516\}.

Conclusión

La conclusión es clara: usted tiene una paciencia pa que podríamos modelar como pa\rightarrow\infty, dado que ha llegado hasta aquí 🙂

Ligeramente más en serio, el número medio de enlaces que se caerán si se cae una página al azar de la Web, según el modelo libre de escala de Barabási y Albert, y en el peor de los casos, sería menor de 40, muy alejado del caso en que se caiga un concentrador. Por tanto, la Web es bastante robusta ante caídas de páginas, dado que es libre de escala. Esto también se aplica a otras redes, sobre todo redes sociales (Facebook, Twitter, amistades en el mundo real, etc.).

Obviamente, lo que hemos hecho aquí es un análisis del caso medio; en el peor de los casos, si se cae un concentrador, vamos apañaos 🙂

Anexo

Ah, que no ha tenido suficiente. Bueno, una nota técnica brevísima: usamos la esperanza matemática, que es la medida más apropiada para hacer una predicción (sobre todo si la acompañáramos de la varianza), dado que aunque no da un valor que tenga siquiera que existir en la realidad, sí da “el centro” alrededor del cual debería estar más probablemente la solución buscada. La otra opción sería utilizar la moda, que sí nos daría el valor existente que tuviera más probabilidad de suceder, aunque dado que la moda se define con una función no lineal (el máximo), es difícil hacer álgebra con ella.

Facebooktwitterredditlinkedintumblrmail