Facebook: infección y contagio

Una característica típica en las redes es la llamada "influencia" donde un determinado usuario de Facebook o Twitter (por ejemplo)  influyen de cierta manera en los demás usuarios. Para estudiar este efecto el profesor Chiang usa un modelo de dependencia topológica, es decir considera a los usuarios como nodos conectados por medio de links y según la forma en que estos se encuentran conectados y la facilidad para establecer nuevas conexiones determina la influencia de cada cual.

En números Facebook tiene alrededor de 900 millones de usuarios y Twitter cerca de 500 millones, en cifras de 2012, esa es la cantidad de nodos de las respectivas redes. Ambos sistemas usan links direccionales donde seguir a alguien no implica que esa persona nos siga de vuelta. El valor económico de la influencia es importante por ejemplo en las campañas de marketing viral, donde se plantan algunos nodos "semilla".

La idea es que ciertos nodos -por su ubicación- dan mayor probabilidad que la semilla produzca un contagio, por eso es impoetante estudiar la topología de la red. Un ejemplo de como influye la topología es la influencia de la familia Medici, cuyo arbol genealogico muestra claramente que estaban en un nodo privilegiado por sus relaciones familiares.

Las topologías de red se pueden representar en grafos y matrices -igual que al calcular el Pagerank de Google- existen grafos con enlaces direccionales y bi direccionales. De la misma manera los patrones de conectividad de un grafo se pueden representar en una matriz, lo que permite manipularlos con operaciones algebraicas. Así se puede construir una matriz donde cada valor Aij será 1 si hay un link entre i-j y 0 si no hay un link entre estos nodos.

Para estudiar como se propaga la influencia según la topología de una red se pueden usar dos enfoques tomados de la medicina: los modelos de contagio  y los modelos de  infección.

Los modelos de contagio se dan por condiciones de conexión que los hacen accesibles a otros, de manera similar a la familia Medicis.  En estos casos es importante que los nodos se aglomeran en clusters y algunos tiene una posición privilegiada para contagíar bien sea por su centralidad o por el alcance de sus links. Esta propiedad llamada closeness centrality del nodo i se denota por Ci.

También existe la betweeness centrality, que es cuando un nodo está en medio del camino más corto entre otros nodos esto se denota por Bi. La importancia de un nodo se llama centrality y en cierto modo refleja que tiene alguna clase de acceso privilegiado o superior a los demás por su topología. Una de las medidad de centralidad o importancia es la que usa Google en el Pagerank calculando el eigenvector y el eigenvalor para clasificar las páginas web. Otras dos medidad de importancia de un nodo son la cercanía (o sea cuantos links cercanos lo unen con otros nodos) y el diámetro, que por el contrario es la cualidad de conectarse con cluster lejanos.

Así para modelos de contagio existen cuatro posibles métricas, según que clase de características estamos más interesados, todas basadas en la posición del nodo dentro de la topología de la red.

Los modelos de infección en cambio, estudian la transición de un estado a otro en el tiempo, son continuos y se tratan usando ecuaciones diferenciales. Se dice que estos son modelos basados en la población. Para la infección se definen tres estados: (S)usceptible, (I)nfectado y (R)epuesto/inmunizado. Que en redes corresponderían a un usuario que no ha sido influenciado, que está siendo influenciado y que ya fue influenciado por otro usuario, pero se "recuperó". Beta es la tasa en que un nodo se infecta y gama la tasa en que se recupera. La ecuación de este modelo de infección es:

dS(t)/dt=-BetaS(t)I(t) y su solución es:

I(t)=(I(0)e^Betat)/(S(0)+I(0)e^Betat), graficamente es logarítmica creciente

Esto en el caso sencillo que todos se infectaran y nadie se recupere. La curva llena es de los suseptibles S(t) y la punteada de los infectados I(t). Lo interesante de estas curvas logarítmicas es que parten cóncavas y en cierto punto cambian de sentido transformándose en convexas, donde ambas curvas se juntan es el punto de inflexión. En las curvas reales, conciderando la recuperación tenemos que S(t) cae y R(t) sube hasta que todos se recuperan (o mueren) en el intermedio los infectados I(t) suben a un máximo y a partir de cierto punto comienzan a caer.

El contagio es un cambio binario, alguien se contagia o no por la influencia de otro, la infección en cambio es un continuo en el tiempo donde alguien que es suceptible se infecta y eventualmente se recupera quedando o no inmunizado. 

El modelo de infección resuelto con ecuaciones diferenciales no considera la topología de la red porque se trata de como ocurre la infeción solo entre dos nodos, incluír la topología de toda la red complica bastante las cosas porque se deben estudiar probabilidades de ser infectado, con esto el modelo se hace intratable y hay que usar distintas aproximaciones, después de sucesivas aproximaciones se llega a una ecuación diferencial con matrices matemáticamente tratable como uestra la figura

Claro que estos modelos super simplificados presentan una utilidad limitada y existe una gran brecha entre la teoría y la práctica, pero sirven para hacerse una idea de como funcionan los mecanismos de contagio e infección en toda clase de redes.