Comprendiendo la influencia de todos los nodos en una red
Glenn Lawyer
Sci Rep. 2015; 5: 8665.
Publicado online 2 Mar 2015. doi:
10.1038/srep08665
Resumen
Las medidas de centralidad tales como el grado, k-shell o centralidad de los valores propios pueden identificar los nodos más influyentes de una red, pero raramente son precisos en cuantificar el poder de propagación de la gran mayoría de los nodos que no son muy influyentes. El poder de propagación de todos los nodos de la red se explica mejor al considerar, a partir de una perspectiva epidemiológica de tiempo continuo, la distribución de la fuerza de infección que genera cada nodo. La métrica resultante, la fuerza esperada, cuantifica con precisión el poder de propagación de nodos bajo todos los modelos epidemiológicos primarios a través de una amplia gama de redes de contacto humano arquetípicas. Cuando la energía del nodo es baja, la influencia es una función del grado vecino. A medida que aumenta el poder, el grado propio de un nodo se vuelve más importante. La fuerza de esta relación es modulada por la estructura de la red, siendo más pronunciada en redes estrechas y densas típicas de redes sociales y debilitándose en redes de asociación más amplias y flexibles como Internet. La fuerza esperada se puede calcular independientemente para los nodos individuales, haciéndolo aplicable para las redes cuya matriz de la adyacencia es dinámica, no bien especificado, o abrumadoramente grande.
Las redes se han convertido en el principal enfoque para describir los procesos de propagación como las epidemias o la transferencia de información porque expresan la heterogeneidad de las interacciones características de muchas actividades humanas1. Treinta años de innovación han refinado nuestra capacidad de identificar nodos que son altamente influyentes en el resultado de casi cualquier proceso de propagación en una red dada a través de características tales como centralidad de intermediación2,3, autovalor de centralidad4, grado5 o k-shell6. Sin embargo, los nodos altamente influyentes son raros por definición, y las medidas listadas no son informativas para la gran mayoría de los nodos de la red. Estas medidas de centralidad sólo clasifican nodos y no están diseñadas para cuantificar el poder de propagación6,7,8. Si bien los rankings identifican con precisión los pocos nodos altamente influyentes, pueden subestimar considerablemente el poder de propagación de los nodos que no son hubs9. Tampoco estas clasificaciones incorporan explícitamente la dinámica de los procesos de propagación10,11. Esto deja abierta la cuestión de cuantificar el poder de propagación de los nodos no altamente influyentes, mucho más numerosos y, de hecho, comprender la naturaleza del poder de propagación de nodos en sí. Dado que los nodos altamente influyentes rara vez originan procesos de propagación, ya se trate de enfermedades patógenas12,13, ideas innovadoras14 o charlas15, existe un profundo hambre intelectual y una utilidad práctica para medir y comprender con precisión el poder de propagación de cada nodo en una red.
La potencia de propagación de un nodo es la fuerza con la que puede empujar un proceso de propagación al resto de la red. Esta definición puede hacerse más precisa por referencia a los modelos epidemiológicos comunes de propagación. En un proceso de propagación susceptible-infectado (SI) sin recuperación, que inevitablemente alcanza todo el componente conectado de la red, el poder de propagación del nodo de la semilla predice el retraso antes de que se alcance la mitad (o algún otro porcentaje grande) de la red. En un proceso con recuperación al estado susceptible (SIS) o inmune (SIR), el poder de propagación se correlaciona con la probabilidad de que un nodo pueda sembrar una epidemia, dado que la proporción de la tasa de transmisión por contacto con la tasa de recuperación permite , Pero no garantiza, una epidemia. Cuando esta relación excede el rango crítico, la dinámica se aproxima al sistema SI como un caso limitante.
Recientemente se han propuesto varios enfoques para cuantificar el poder de propagación de todos los nodos, incluyendo la accesibilidad16,17, la influencia dinámica11 y el impacto8. Esto amplía los enfoques anteriores para medir la centralidad incorporando explícitamente la dinámica de la propagación. La accesibilidad es una forma modificada de grado jerárquico que controla tanto las probabilidades de transmisión como la diversidad de caminatas de una determinada longitud fija17. La influencia dinámica, al igual que la centralidad de los valores propios, es la proporción de paseos infinitos a partir de cada nodo, donde los pasos a pie se escalan de tal manera que se espera que la dinámica lineal del sistema converja a un estado estacionario no nulo11. El impacto suma, a través de longitudes de caminata crecientes, la probabilidad de transmisión al nodo final de la caminata y que el nodo final no ha sido visitado previamente por una caminata más corta8. Se ha demostrado que estas nuevas métricas de poder de dispersión son distintas de las medidas de centralidad anteriores y están más correlacionadas con los resultados epidémicos8,11,18. Sin embargo, mantienen el fundamento común de los enfoques más habituales de la centralidad, contando los paseos por la red10,19,20,21. Como las caminatas se cuentan utilizando potencias de la matriz de adyacencia, la propagación se observa sólo en tiempo discreto.
La epidemiología, por el contrario, estudia la dinámica del tiempo continuo de la fuerza de infección (FoI), definida como la tasa actual a la que se infectan los nódulos susceptibles22. En los modelos de red, el FoI es directamente proporcional al número actual de bordes entre nodos infectados y susceptibles. La distinción crítica entre FoI y paseos es que la FoI está determinada por el número de bordes infectados-susceptibles, independientemente de su distancia del nodo de la semilla. La distinción crítica entre el tiempo continuo y el tiempo discreto es que el tiempo continuo permite la resolución hasta las dos primeras transmisiones, un nivel que no se expresa fácilmente en un marco de tiempo discreto donde pueden ocurrir transmisiones múltiples en cada paso de tiempo. La distinción es aguda, ya que el número de eventos por paso de tiempo crece a una tasa de doble exponencial en redes libres de escala23, el tipo de red más representativa de las estructuras humanas24 y tal vez incluso la propia vida25.
La perspectiva epidemiológica en tiempo continuo sugiere que la potencia de propagación de nodos puede cuantificarse con exactitud resumiendo adecuadamente la distribución del número de bordes susceptibles a infección después de un pequeño número de eventos de transmisión que surgen de un nodo de semilla en una red de otra manera completamente susceptible; Es decir, por la FoI esperada generada por ese nodo. Aquí proponemos una medida de este tipo, denominada fuerza esperada (ExF), y demostraremos que ésta supera la centralidad de accesibilidad, k-shell y valores propios en la predicción de los resultados epidémicos en los procesos de separación SI, SIS y SIR, tanto discretos como continuos -hora. La base en la estructura de vecindad local significa que la ExF es aplicable incluso cuando la matriz de adyacencia completa es desconocida o intrínsecamente incognoscible. Naturalmente, la métrica se extiende a redes ponderadas y dirigidas. Más importante aún, la fuerza esperada es capaz de iluminar los factores responsables de la potencia de propagación del nodo.
Resultados
Definición de la fuerza esperada
La fuerza esperada es una propiedad de nodo derivada de la topología de red local, independiente del resto de la red o de cualquier proceso de propagación específico. Se define formalmente como sigue. Considere una red con un nodo infectado i y todos los nodos restantes susceptibles. Enumerar todos los clústeres posibles 1, ..., J de nodos infectados después de los eventos de transmisión x, suponiendo que no hay recuperación (Ver Figura 1). En términos generales, x = 2 es suficiente y asumido para el resto de este manuscrito. Por lo tanto, J incluye todas las combinaciones posibles de i más dos nodos a la distancia uno de i, e i más un nodo a la distancia uno y uno a la distancia dos. La enumeración es sobre todos los posibles pedidos de los eventos de transmisión. Dos vecinos de la semilla (a y b) forman dos grupos ([i → a, i → b] y [i → b, i → a]) o, si a y b también comparten un borde, cuatro clusters. Después de dos transmisiones sin recuperación, la FoI de un proceso de propagación sembrado desde el nodo
i es una variable aleatoria discreta que toma un valor en
(d1, …, dJ), permitiendo la constante de proporcionalidad igual a la velocidad de transmisión del proceso. La fuerza esperada de la infección puede ser aproximada por la entropía de la dj después de la normalización
Donde i se refiere al nodo de la semilla y
.
Figura 1. Derivación la fuerza esperada de los posibles resultados de dos transmisiones.
Derivar la fuerza esperada de los posibles resultados de dos transmisiones. Esta red estará en uno de los ocho posibles estados después de dos transmisiones desde el nodo semilla (rojo). Se ilustran dos estados, donde la semilla ha transmitido a los dos nodos naranja a lo largo de los bordes negros sólidos. Cada estado tiene un número asociado de bordes (naranja punteado) a los nodos susceptibles (azul), el grado de agrupación. Los estados que contienen dos vecinos de la semilla (panel a) pueden formar de dos maneras o, si forman parte de un triángulo, cuatro formas. Los ocho estados de red asociados con el nodo de semilla representado se forman a partir de trece posibles clústeres de transmisión. La fuerza esperada de un nodo de la semilla es la entropía de la distribución del grado (normalizado) del cluster sobre todos (aquí 13) cluster posibles de la transmisión.
La entropía es necesaria para generar el valor esperado debido a la extrema variabilidad en la forma, número de modos y número de términos en las distribuciones de dj para diferentes nodos de semilla. Las redes complejas tienen distribuciones de grados sin escala. Los momentos de las distribuciones libres de escala son divergentes, lo que implica que la distribución de dj puede no tener un valor medio en el sentido tradicional. La entropía es una herramienta estándar para domar las distribuciones inestables debido a su estrecha relación con las funciones de generación de acumuladores, motivando el uso de la Ecuación 1 para generar un valor cuasi esperado de la FoI. Se puede hacer una analogía con el uso de la entropía en la física estadística para resumir el macrostate de un sistema (por ejemplo, la presión de un gas) basado en la distribución de sus microestados (las posiciones y los momentos de las moléculas en el gas). La analogía es que la presión es una combinación del número y el calor de las moléculas, así como la fuerza esperada de un nodo es una combinación del número de racimos de transmisión posibles que puede formar y el FoI generado por cada racimo. Un análisis en profundidad de la relación entre entropía, cumulantes y física estadística se puede encontrar en la revisión de Touchette26.
Se recomienda el ajuste x = 2 pero no es necesario. Las investigaciones complementarias demuestran que el aumento del número de transmisiones más allá de dos agrega muy poca información al tiempo que aumenta el coste computacional (véase Nota Complementaria 1), de acuerdo con otras métricas de potencia de propagación propuestas8,11 y consistentes con la influencia decaída de trayectorias más largas en los cálculos de El autovalor, el subgrafo y las centralidades relacionadas4,7,20,21. En ciertos casos, sin embargo, puede ser deseable considerar más eventos de transmisión. Por ejemplo, un nodo al final de una cadena de longitud dos sólo puede formar un grupo de transmisión de tamaño dos, por lo tanto su fuerza esperada es cero. La comparación de dos de estos nodos requiere el ajuste x = 3, en cuyo caso un subíndice se puede utilizar para la claridad (por ejemplo, ExF3).
Una modificación puede estar en orden para los procesos SIS / SIR, inspirados en lo siguiente. Imagine un nodo con grado uno conectado a un hub. Mientras que tal nodo tendrá una fuerza esperada alta, su probabilidad de realizar esta fuerza depende enteramente de la transmisión al cubo antes de la recuperación. Tales nodos son comunes en redes sociales densas. Por ejemplo, el 84% de los 225K nodos de una red de correo electrónico de la UE27 tienen grado uno. En tales redes, puede ser útil dar cuenta de la dependencia de la transmisión inicial multiplicando el ExF por el logaritmo del nodo de la semilla después de primero reescalar el grado de la semilla por algún factor α> 1.
El cambio de escala se basa en que el log de uno es cero, y el ExFM es más informativo en redes donde muchos nodos tienen grado uno. El factor de reescalado debe ser mayor que uno, y también debe ser pequeño para evitar sobrevalorar la influencia del grado. En el resto de este manuscrito, utilizamos α = 2, el entero más pequeño que satisface estos criterios. Nota complementaria 2 muestra que el cálculo de la ExFM para α que van desde 1.0001 a 16 no altera sustancialmente la métrica, ya que todas las variaciones muestran correlaciones superiores a 0,99 a ExFM calculado con α = 2.
El cálculo directo de la fuerza esperada tiene complejidad en el tiempo
. donde
n1 y
n2 son el número de vecinos a distancia uno y dos de la semilla. Es difícil comparar analíticamente una complejidad de tiempo calculada en nodos individuales con complejidades de tiempo cuyo cálculo se basa en toda la matriz de adyacencia. Además, puesto que la métrica se basa sólo en información local, puede computarse de manera masiva paralela, o sólo se calcula en nodos de interés. También permite cálculos (parciales) significativos incluso en gráficos masivos, es decir, aquellos cuyo tamaño sobrepasa la memoria de la computadora. No obstante, se requiere alguna comparación con los tiempos de ejecución de las métricas existentes. Comparamos el tiempo mediano de ejecución de más de cincuenta redes de Pareto de 1.000 nodos para todas las medidas discutidas aquí. El tiempo de ejecución en cada red se mide como el tiempo de cálculo mediano sobre diez ejecuciones en esa red, con el tiempo de cómputo medido a una precisión de sub-microsegundo28. El cálculo de la ExF para todos los nodos que no son de hub toma 0.16 segundos. La k-shell se calcula en el 2% de ese tiempo (0,003 segundos), y la centralidad del valor propio en el 20% de ese tiempo (0,03 segundos). El cálculo de la accesibilidad demora varios cientos de veces más. El benchmarking se repite con el mismo protocolo en redes Pareto de 10.000 nodos. Los aumentos en el tiempo de ejecución de la k-shell (6x), la centralidad del valor propio (9x) y la fuerza esperada (16x) tienen una correspondencia aproximadamente lineal con el aumento de diez veces en el número de nodos de la red. Recuérdese que la complejidad de tiempo probada para el k-shell y el tiempo esperado para la centralidad de valores propios son O (| V | + | E |), es decir, lineales. Como era de esperar, la accesibilidad no escala bien, con un aumento de diez veces en el tamaño de la red conduce a un aumento de 265 veces en la mediana de tiempo de ejecución. Recordemos que se calcula tomando potencias de la matriz de adyacencia, es decir, algo peor que O (| V | 2.4). Benchmarking se realizó dentro del entorno de programación R29 que se ejecuta en una computadora portátil de productos básicos. K-shell y eigenvalue cálculos se calculan a través de funciones estándar en el paquete Igraph30. La accesibilidad se calcula en código nativo R29 utilizando la multiplicación de matriz dispersa del paquete Matrix 1.0-1031. La fuerza esperada se calcula en código C a través de una interfaz R
El código de ejemplo que proporciona una implementación de la fuerza esperada está disponible en https://github.com/glennlawyer/ExpectedForce.
Correlación con los resultados de la epidemia
Medimos las correlaciones entre la fuerza esperada y los resultados de la epidemia en cinco familias de redes simuladas elegidas de tal manera que sus densidades y distribuciones de grado abarcan una amplia gama de estructuras de contacto humano, como se muestra en la Tabla 1. Cien redes aleatorias de 1.000 nodos se generan en cada familia . Se realizan más comparaciones usando un conjunto de veinticuatro redes del mundo real que van desde 1.133 a 855.800 nodos, como se muestra en la Tabla 2. Los resultados de la epidemia son el tiempo hasta la mitad de la cobertura de los procesos SI y el potencial epidémico para los procesos SIS y SIR. Estos se observan mediante la simulación de múltiples epidemias en tiempo continuo y discreto de un número de nodos de semillas en cada red. Las correlaciones se miden entre estos resultados y la fuerza esperada, ExFM, accesibilidad, centralidad de eigenvalue, y la k-shell de los nodos de la semilla. Motivaciones para estas opciones y detalles adicionales se dan en los métodos.
Tabla 1. Familias de redes simuladas. El diámetro medio, la densidad gráfica media y el rango medio cuantitativo empírico del 65% del mayor autovalor para las diferentes familias de la red. Las redes de co-compra de Pareto y Amazon tienen una estructura grande y floja con un autovalor bajo, lo que sugiere una menor susceptibilidad inherente a las epidemias que las redes de colaboración más pequeñas y más densas; El mapa de Google de Internet está en el medio. Medios y desviaciones estándar se calculan a lo largo de 100 redes simuladas con 1.000 nodos
| diámetro | densidad | cuantil 65% |
|---|
| Pareto | 11.6 ± 1.0 | 3.2 e-04 | 7.1–10.1 |
| Amazon [42] | 7.2 ± 0.4 | 6.9 e-04 | 10.1–13.7 |
| Internet [42] | 7.0 ± 0.5 | 9.4 e-03 | 25.2–35.2 |
| Astrophysics [27] | 5.5 ± 0.6 | 2.1 e-02 | 54.5–61.9 |
| Facebook [44] | 5.5 ± 0.5 | 2.4 e-02 | 65.2–73.7 |
Tabla 2. Redes del mundo real. El número de nodos, percentil 90 diámetro efectivo, y la densidad de las redes reales. Las redes se descargaron de la Colección de Grandes Redes de Stanford (SNAP), la colección Alex Arena (AA) y el sitio web del Instituto Max Planck para Sistemas de Software (MPI), que a su vez dan crédito a la citada publicación para la red
| nodos | diámetro | densidad | fuente |
|---|
| PGPgiantcompo | 10680 | 10.0 | 4.26 e-4 | AA [46] |
| amazon0302 | 262111 | 11.1 | 0.26 e-4 | SNAP [42] |
| amazon0601 | 403364 | 7.6 | 0.30 e-4 | SNAP [42] |
| ca-AstroPh | 17903 | 5.0 | 12.30 e-4 | SNAP [27] |
| ca-CondMat | 21363 | 6.5 | 4.01 e-4 | SNAP [27] |
| ca-GrQc | 4158 | 7.6 | 15.53 e-4 | SNAP [27] |
| ca-HepPh | 11204 | 5.8 | 18.74 e-4 | SNAP [27] |
| ca-HepTh | 8638 | 7.4 | 6.65 e-4 | SNAP [27] |
| cit-HepPh | 34401 | 5.0 | 7.11 e-4 | SNAP [47] |
| cit-HepTh | 27400 | 5.3 | 9.38 e-4 | SNAP [47] |
| com-dblp | 317080 | 8.0 | 0.21 e-4 | SNAP [48] |
| email-EuAll | 224832 | 4.5 | 0.13 e-4 | SNAP [27] |
| email-Uni | 1133 | 4.3 | 85.00 e-4 | AA [49] |
| facebooklcc | 59691 | 5.6 | 4.09 e-4 | MPI [44] |
| loc-brightkite | 56739 | 6.0 | 1.32 e-4 | SNAP [50] |
| loc-gowalla | 196591 | 5.7 | 0.49 e-4 | SNAP [50] |
| p2p-Gnutella31 | 62561 | 6.7 | 0.76 e-4 | SNAP [27] |
| soc-Epinions1 | 75877 | 5.0 | 1.41 e-4 | SNAP [51] |
| soc-Slashdot0902 | 82168 | 4.7 | 1.49 e-4 | SNAP [43] |
| soc-sign-epinions | 119130 | 4.9 | 0.99 e-4 | SNAP [52] |
| web-Google | 855802 | 8.1 | 0.12 e-4 | SNAP [43] |
| web-NotreDame | 325729 | 9.4 | 0.21 e-4 | SNAP [53] |
| web-Stanford | 255265 | 9.7 | 0.60 e-4 | SNAP [43] |
| wiki-Vote | 7066 | 3.8 | 40.36 e-4 | SNAP [52] |
La fuerza esperada es altamente predictiva de todos los resultados de la epidemia en todas las redes probadas, simuladas y reales. La correlación media con los resultados del proceso del SI es del 83% en las redes simuladas y del 74% en las redes reales. Para los procesos con recuperación, la correlación media es del 91% en las redes simuladas y del 82% en las redes reales. Las desviaciones estándar sobre las cien redes simuladas en cada familia son típicamente 0,02-0,03. Los límites de confianza del 95% en redes reales están en el mismo rango. En todos los casos la ExF (o ExFM) supera significativamente la accesibilidad y la centralidad de los valores propios (diferencia en las correlaciones medias mayores que la desviación estándar de la media más alta). Típicamente supera a la k-shell, superando significativamente en 82 casos, mostrando un rendimiento equivalente en 11 casos (diferencia en las correlaciones medias menores que la desviación estándar de la media más alta) y un rendimiento significativamente menor en 6 casos (redes SIS- C, SIR-C, SIR-D, simulación de redes de astrofísica SIR-D, simulación de redes Facebook SIR-D, "e-mail-EUAll" de la red SI). El rendimiento de la k-shell fue sorprendentemente fuerte, dado que dos estudios previos de grupos independientes han observado un rendimiento bastante pobre para esta métrica11,18. Las correlaciones observadas en 100 redes simuladas en cada familia se muestran en parcelas de violín (Figura 2); La información se duplica en forma tabular en la Tabla Suplementaria 5. Asimismo, las correlaciones medidas y sus errores estándar para todas las redes reales se muestran en la Figura 3, presentados en forma tabular en las Tablas Suplementarias 6, 7 y 8, y representados individualmente en Figuras Suplementarias 1-6.
Figura 2. Correlación de los indicadores de potencia de propagación a los resultados de la epidemia en redes simuladas.
Las parcelas de violín muestran la distribución de los valores de correlación observados para cada resultado del proceso de propagación en cada familia de la red. La fuerza esperada y ExFM (tonos naranja) son consistentemente fuertes, con correlaciones medias mayores de 0,85 y pequeña varianza. Las otras medidas (k-shell, centralidad de valores propios y accesibilidad, tonalidades azul-verde) muestran tanto valores medios más bajos como mayores varianzas, como se observa en la posición y extensión vertical de sus violines. Cada violín resume las correlaciones calculadas en 100 redes simuladas. Los procesos de extensión (eje x) tienen sufijo para indicar simulaciones en tiempo continuo (-C) o discreto (-D). El resultado de la epidemia para los procesos SI es el tiempo hasta que la mitad de la red está infectada. Para los procesos SIS y SIR es la probabilidad de que se observe una epidemia.
Figura 3. Correlación de las medidas de poder de propagación a resultados epidémicos en redes reales.
Las gráficas de barras de puntos y errores muestran la correlación observada y el intervalo de confianza del 95% entre cada medida y el resultado del proceso de propagación en las 24 redes reales. La fuerza esperada y ExFM (tonos naranja) muestran un buen rendimiento, superando sistemáticamente las otras métricas (k-shell, eigenvalue centrality, y accesibilidad cuando se computan, tonos azul-verde). El resultado de la epidemia para los procesos SI es el tiempo hasta que la mitad de la red está infectada. Para los procesos SIS y SIR es la probabilidad de que se observe una epidemia. El sufijo "-D" indica procesos de propagación simulados en tiempo discreto. Los paneles individuales se dan como figuras separadas (más grandes) en las Figuras Suplementarias 1-6.
El poder predictivo de la fuerza esperada es robusto a la variación en la estructura de la red. La teoría detrás de la ExFM sugiere que la ExF podría perder el rendimiento de los procesos SIS / SIR en redes más densas, sin embargo, la correlación media para los procesos SIS de tiempo continuo apenas cambia entre las redes Pareto / Amazonas (0.93 / 0.95) y la densa Astrofísica / Facebook (0,92 / 0,90). Como se esperaba, el poder predictivo de la ExFM mejora en las redes más densas (correlaciones medias: Pareto / Amazon 0.89 / 0.92, Astrofísica / Facebook 0.94 / 0.95). La precisión de la métrica de accesibilidad, por el contrario, se derrumba para todos los procesos de propagación en las redes densas (correlación media en todos los procesos de propagación: Pareto / Amazon 0.74 / 0.90, Astrofísica / Facebook 0.28 / 0.20). Para la accesibilidad en redes densas concluyó que los procesos de propagación sembrados de nodos con baja accesibilidad no son capaces de entrar en la fase epidémica18. Nuestros resultados muestran que este no es el caso, ya que estos nodos tienen un potencial epidémico pequeño pero observable que la fuerza esperada es capaz de capturar y cuantificar. El rendimiento de la k-shell y la centralidad de los valores propios también está fuertemente influenciada por la estructura de la red. Para los procesos SIS / SIR, ambos mostraron una media más alta y una variación fuertemente reducida en las redes más densas. En un interesante contraste, la potencia predictiva de la k-shell para los procesos SI se reduce en redes más densas. El rendimiento de la centralidad de valores propios también varía según el proceso de propagación, mostrando su mejor rendimiento en modelos SIS de tiempo discreto, aunque esta variación es modulada por la densidad de la red. Otros dos grupos independientes han observado que las relaciones entre las clasificaciones de centralidad y los resultados epidémicos están fuertemente influenciadas por la estructura de la red y los parámetros de los procesos de extensión8,9, lo que conduce a los autores de la ref. 9 para concluir que estas medidas subestiman gravemente el impacto epidémico de los nódulos estructuralmente periféricos.
Grafos ponderados
La fuerza esperada se generaliza a los gráficos con enlaces ponderados, donde suponemos que los pesos de los bordes corresponden a las probabilidades de transmisión por enlace. Utilice estos pesos para calcular la probabilidad de cada forma en que podría ocurrir cada grupo y redefinir el grado de agrupación como la suma de todos los pesos de los bordes que salen de ese grupo. La extensión a los gráficos dirigidos también es directa; Limitar la enumeración a los bordes que conducen desde un nodo infectado a un nodo susceptible.
Probamos esta generalización calculando la fuerza esperada ponderada y no ponderada en redes de 1.000 nodos con distribuciones de grados de Pareto (1,2,3) y pesos de los bordes elegidos de acuerdo con una de las tres distribuciones siguientes: uniformemente distribuidas entre uno y tres, uniformemente distribuidas entre uno y tres Diez, y distribuido exponencialmente con la tasa unitaria, pesos redondeados al entero más cercano. Cincuenta redes fueron simuladas para cada distribución de pesos de borde. La correlación entre el exF ponderado y no ponderado fue mayor de 0,99 para todas las distribuciones de ponderación de los bordes de red evaluadas. Como se esperaba de la estrecha correlación, el ExF ponderado y no ponderado no mostró ninguna diferencia significativa en la capacidad predictiva, que se mantuvo alta. Las correlaciones observadas entre la fuerza esperada del nodo y el potencial epidémico en los procesos de SIS de tiempo discreto fueron 0.88 / 0.89 ± 0.03 (no ponderado/ ponderado ExF) bajo el esquema uniforme-3, 0.83 / 0.04 ± 0.03 bajo el esquema uniforme-10 y 0.80 / 0.79 ± 0,05 bajo el esquema de ponderación distribuido exponencialmente.
Discusión
La fuerza esperada predice todos los tipos de resultados epidemiológicos con alta precisión en una amplia gama de estructuras de red y procesos de propagación. La baja varianza en las correlaciones observadas sobre múltiples modelos simulados de red y epidemia muestra que la medida es robusta, al igual que los estrechos límites de confianza en las redes del mundo real. Entonces, ¿qué nos dice sobre la naturaleza del poder de propagación de nodos? La definición de la fuerza esperada implica que el poder de propagación está determinado tanto por el grado del nodo como por el grado de sus vecinos, y que la influencia relativa de estos dos factores es diferente para los nodos de potencia de propagación baja frente a alta. Los nodos más débiles ganan la fuerza que tienen de sus vecinos, mientras que los nodos más influyentes obtienen su fuerza de su gran número de conexiones. Estas relaciones se ven acentuadas por la densidad de la red.
Esto es un resultado de la combinatoria detrás de la enumeración sobre los racimos de la transmisión. El número de rutas con un borde (p1) contribuye cuadráticamente al número de grupos de transmisión, mientras que el número de trayectos de dos bordes (p2) contribuye linealmente, ya que J = p1 * (p1 - 1) + p2. El grado del nodo es exactamente p1. El grado vecino es como máximo p2. Los nodos más débiles tienden a tener un grado más bajo, por lo tanto, el grado vecino contribuye más fuertemente a su fuerza esperada. La influencia de la densidad de la red viene en parte de la sensibilidad de la ExF a los motivos de la red tales como triángulos y cuadrados. Cada triángulo es trazada por dos trayectorias con dos aristas, aumentando la proporción de p2 asociada con el grado del nodo. Más importante aún, el ExF es la entropía de la conectividad hacia adelante de cada grupo de transmisión. Un triángulo genera cuatro grupos de este tipo, cada uno de los cuales tiene grado de agrupación idéntico. Del mismo modo, cada cuadrado representa dos grupos. Estos motivos de red, que son más comunes hacia los núcleos de las redes densas, reducen la disparidad de las distribuciones de grados de cluster, aumentando así la entropía. La combinatoria se vuelve más complicada cuando la enumeración se basa en más de dos transmisiones, pero estos patrones generales permanecen. Estas relaciones se pueden observar trazando ExF en función de las sumas de los grados de nodos a una distancia geodésica creciente de la semilla (Figura 4, Tabla Suplementaria 3).
Figura 4. El poder de dispersión es un factor del grado de primer y segundo orden de un nodo.
La representación gráfica de la fuerza esperada (eje x) en función del grado del nodo (naranja), la suma del grado de todos los vecinos (azul) y la suma del grado de todos los vecinos a la distancia 2 (verde) El grado del vecino tiene una fuerte correlación con ExF, mientras que para los nodos con alto ExF su propio grado está más estrechamente correlacionado. El resultado se acentúa en redes de colaboración más densas en comparación con redes de Pareto más difusas. La correlación entre ExF y grado vecino es de 0,94 ± 0,01 en las redes de colaboración y baja a 0,84 ± 0,02 en las redes de Pareto (media tomada en 50 redes).
El enfoque adoptado por la fuerza esperada es fundamentalmente diferente del adoptado por la mayoría de las medidas de centralidad. Las medidas de centralidad establecidas típicamente para producir una clasificación que identifica los nodos más influyentes en la red, bajo la suposición de que los nodos altamente influyentes son aquellos con la suma máxima de algún tipo de caminata8,10,19,20,21. La elección del tipo apropiado, la escala y la longitud de las caminatas contienen suposiciones implícitas con respecto a los flujos de red10, estructura de cohesión19 y / u otras características topológicas20, 21 de la red. La k-shell es una ligera excepción, ya que originalmente se pretendía precipitar las regiones más cohesivas de la red en lugar de clasificar explícitamente nodos dentro de regiones cohesivas32, sin embargo, ahora se reconoce como una de las mejores medidas de centralidad para identificar una red Más influyentes6. La difusión de las métricas de potencia generaliza el marco de conteo de caminatas al incluir explícitamente las probabilidades de transmisión al escalar las caminatas8,11,16,17. La pregunta que no se plantea es si el tipo, la escala y las longitudes de los recorridos más adecuados para identificar los nodos más importantes se aplican igualmente al resto de la red. En la medida en que la elección óptima de los factores depende de la topología de la red, la diferencia en la topología entre el núcleo y la periferia sugiere que las opciones adecuadas al núcleo son menos apropiadas para el resto de la red.
Tanto la combinatoria detrás de la fuerza esperada como la caminata que cuenta detrás de la mayoría de las medidas de centralidad coinciden en que los nodos influyentes son aquellos que combinan alto grado con una preponderancia de vecinos influyentes. El ExF tiene correlación de alto rango con la centralidad de los valores propios y el k-shell (0,62-0,92 a través de las familias de la red simulada, véase la Nota Suplementaria 3). Del mismo modo, el ExF tiene un acuerdo del 60-90% con la centralidad del autovalor en los diez nodos de la red y un 100% de acuerdo con el k-shell. La diferencia entre el recuento de la caminata y la fuerza esperada es que la fuerza esperada adopta la influencia relativa de diferentes caminatas y longitudes de caminata basadas en la conectividad local, mientras que los enfoques basados en funciones de la matriz de adyacencia aplican un protocolo fijo. La centralidad del autovalor es el grado del nodo ponderado, donde los pesos son la importancia de los vecinos4,7. Pero la centralidad de los valores propios es estrictamente una medida global, incapaz de distinguir variaciones más sutiles en la estructura local7,21. La k-shell erosiona el grado del nodo para que coincida con el número de vecinos con grado similar. Dado que esto descarta la información restante sobre el grado individual de nodos dentro de un shell común, la precisión de sus predicciones está fuertemente influenciada por el número de conchas en la red. La accesibilidad combina el grado del nodo y del vecino en una medida del número de nodos que pueden ser alcanzados por caminatas de una longitud dada17. Pero este enfoque tiene dificultades para cuantificar nodos en redes densas de diámetro pequeño, lo que acentúa las diferencias entre la topología central y periférica.
La fuerza esperada ofrece ventajas adicionales sobre el poder de propagación existente y las medidas de centralidad en que su cálculo depende solamente de la topología local. Esto permite que los resultados de la epidemia en toda la red se prediquen con alta precisión, incluso cuando sólo una pequeña parte de la red es conocida. Es raro que se conozca completamente la estructura completa de una red real; Típicamente la estructura de la red se infiere de observaciones indirectas, incompletas ya menudo sesgadas. La especificación de una matriz de adyacencia es aún más difícil cuando la red subyacente es dinámica. Estos límites tienen implicaciones prácticas. Las estimaciones de la centralidad de los valores propios fluctúan dependiendo de los nodos que se muestre33. Tanto el pagerank34 como el k-shell35 son altamente sensibles a las pertubaciones en la topología de la red, por lo que no son confiables para sistemas incompletos o ruidosos.
La dependencia en un vecindario local es consistente con la teoría establecida que demuestra que el contenido de la información topológica cae rápidamente con la distancia. Bonacich demostró en 1987 que la centralidad del autovalor puede expresarse en términos de sumas sobre recorridos de longitud k, k = 1 ... ∞, estableciendo que la influencia de los paseos debe decaer al menos exponencialmente en k para garantizar la convergencia4. Un trabajo más reciente muestra que casi todas las medidas de centralidad, incluidas las basadas en los resolventes matriciales, pueden expresarse también como sumas infinitas sobre los paseos y que las tasas de desintegración más rápidas que exponenciales suelen estar motivadas20,21. La disminución de la información también puede mostrarse mediante el siguiente ejemplo. Considere una larga cadena lineal de nodos que finalmente se conecta a un hub de red. Sea β la relación de transmisión / recuperación en un proceso con recuperación y Δi la distancia desde el i-ésimo nodo de la cadena al cubo. Si el proceso de propagación alcanza el centro, una epidemia es casi segura. La probabilidad de que esto ocurra es como máximo Un archivo externo que contiene una imagen, ilustración, etc.
El nombre del objeto es srep08665-m5.jpg. Para β <0.1, esta probabilidad es estimable a tres de cuatro decimales usando solamente información local. De manera más general, dado que la propagación de la epidemia es casi instantánea en redes libres de escala23,36, la expectativa es que el paso del tiempo que lleva a un proceso fuera del vecindario local de su origen lo lleva a la mayoría de la red.
La dependencia en una red local, sin embargo, conduce a una debilidad en la fuerza esperada. Una red puede contener comunidades grandes pero dispares. Aquí, un nodo que sirve como un puente entre dos comunidades podría ser capaz de extender un proceso a toda la red con más fuerza que un nodo lejos del puente, incluso cuando el segundo nodo tiene más potencia de propagación (local) que el nodo puente. La naturaleza local de la fuerza esperada lo hace ciego a estas limitaciones topológicas mayores en la propagación.
Este trabajo define el resultado de la epidemia en los procesos SIS / SIR como la probabilidad de que ocurra una epidemia. Esto contrasta con la medida típicamente utilizada, el número medio de nodos infectados (es decir, refs. 6, 8, 9, 11, 17, 18, 37). No estamos convencidos de que la media sea una buena estadística de resumen. En más de 20.000 procesos de propagación SIS simulados en tiempo continuo, ningún proceso que se extinguió alcanzó más de 20 nodos, mientras que los procesos que no se extinguieron alcanzaron la mayoría de la red. Se ha argumentado que tal bifurcación en resultados es predicha por la teoría [38]. Dado que la distribución del número de nódulos infectados se caracteriza por dos modos bien separados, la media se considera mejor como una estimación indirecta de la probabilidad del modo superior. Es esta probabilidad la que medimos directamente como potencial epidémico.
La fuerza esperada predice los resultados epidémicos de las características locales de los nodos específicos en una red específica, con sólo referencia de paso a la naturaleza y los parámetros del proceso de propagación. El trabajo seminal ha abordado la cuestión desde el otro lado. Dado los parámetros de un proceso de difusión de SIR y una clase de redes que se caracterizan por su distribución de grados, existen soluciones exactas para los valores típicos de una serie de resultados epidémicos37, y su tiempo puede expresarse como ecuaciones diferenciales ordinarias apareadas39. Se puede pensar que la potencia de propagación del nodo explica la parte de la varianza alrededor de estos valores típicos que se debe a la elección del nodo semilla.
La fuerza esperada está fuertemente correlacionada con el resultado de la epidemia, superando las métricas existentes de poder de propagación de nodos y centralidad. La medida sólo depende de la topología de la red local, permitiendo su uso en redes dinámicas y estáticas. Para la mayoría de los nodos, el determinante más importante de su poder de propagación es la suma del grado de sus vecinos. A medida que aumenta la potencia del nodo, aumenta la importancia del grado del nodo. Esta relación se acentúa en redes más densas.
Referencias
- Danon L. et al. Networks and the epidemiology of infectious disease. Interdiscip Perspect Infect Dis2011, 284909 (2011). [PMC free article] [PubMed]
- Freeman L. C. Centrality in social networks: Conceptual clarification. Soc Networks 1, 215–239 (1979).
- Friedkin N. Theoretical foundations for centrality measures. Am J Sociol 96, 1478–1504 (1991).
- Bonacich P. Power and centrality: A family of measures. Am J Sociol 92, 1170–1182 (1987).
- Albert R. & Barabási A.-L. Statistical mechanics of complex networks. Rev Mod Phys 74, 47–97 (2002).
- Kitsak M. et al. Identification of influential spreaders in complex networks. Nature Phys 6, 888–893 (2010).
- Estrada E. & Rodríguez-Velázquez J. A. Subgraph centrality in complex networks. Phys Rev E Stat Nonlin Soft Matter Phys 71, 056103 (2005). [PubMed]
- Bauer F. & Lizier J. T. Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach. Europhys Lett 99, 68007 (2012).
- Sikic M., Lancic A., Antulov-Fantulin N. & Stefancic H. Epidemic centrality – is there an underestimated epidemic impact of network peripheral nodes? EPJ B 86, 1–13 (2013).
- Borgatti S. P. Centrality and network flow. Soc Networks 27, 55–71 (2005).
- Klemm K., Serrano M., Eguluz V. M. & Miguel M. S. A measure of individual role in collective dynamics. Sci Rep 2, 292 (2012). [PMC free article] [PubMed]
- Taylor L. H., Latham S. M. & Woolhouse M. E. Risk factors for human disease emergence. Philos Trans R Soc Lond B Biol Sci 356, 983–989 (2001). [PMC free article] [PubMed]
- Reperant L. A. Applying the theory of island biogeography to emerging pathogens: toward predicting the sources of future emerging zoonotic and vector-borne diseases. Vector Borne Zoonotic Dis 10, 105–110 (2010). [PubMed]
- Christensen C. M. The Innovator's Dilemma: When New Technologies Cause Great Firms to Fail (Harvard Business Review Press, Boston, 1997).
- Cha M., Haddadi H., Benevenuto F. & Gummadi K. P. Measuring user influence in Twitter: The million follower fallacy. In: Proc International AAAI Conference on Weblogs and Social Media (2010).
- Travençolo B. & Costa L. d. F. Accessibility in complex networks. Phys Lett A 373, 89–95 (2008).
- Viana M. P., Batista J. L. B. & Costa L. d. F. Effective number of accessed nodes in complex networks. Phys Rev E Stat Nonlin Soft Matter Phys 85, 036105 (2012). [PubMed]
- da Silva R. A. P., Viana M. P. & da Fontoura Costa L. Predicting epidemic outbreak from individual features of the spreaders. J Stat Mech Theor Exp 2012, P07005 (2012).
- Borgatti S. P. & Everett M. G. A graph-theoretic perspective on centrality. Soc Networks 28, 466–484 (2006).
- Estrada E. Generalized walks-based centrality measures for complex biological networks. J Theor Biol263, 556–565 (2010). [PubMed]
- Benzi M. & Klymko C. A matrix analysis of different centrality measures (2013). URL arXiv:1312.6722[math.NA].
- Anderson R. M. & May R. M. Infectious Diseases of Humans: Dynamics and Control (Oxford University Press, Oxford, 1992).
- Fountoulakis N., Panagiotou K. & Sauerwald T. Ultra-fast rumor spreading in social networks. In: Proc Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, 1642–1660 (SIAM, 2012).
- Barabasi A. L. & Albert R. Emergence of scaling in random networks. Science 286, 509–512 (1999).[PubMed]
- Almaas E., Kovcs B., Vicsek T., Oltvai Z. N. & Barabsi A.-L. Global organization of metabolic fluxes in the bacterium escherichia coli. Nature 427, 839–843 (2004). [PubMed]
- Touchette H. The large deviation approach to statistical mechanics. Phys Rep 478, 1–69 (2009).
- Leskovec J., Kleinberg J. M. & Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1 (2007).
- Mersmann O. Microbenchmark: Sub microsecond accurate timing functions. (2013). R package version 1.3-0. URL http://CRAN.R-project.org/package=microbenchmark. (Date of access: 14/02/2014.
- R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2012). URL http://www.R-project.org/ ISBN 3-900051-07-0.
- Csardi G. & Nepusz T. The igraph software package for complex network research. Inter- Journal Complex Systems, 1695 (2006).
- Bates D. & Maechler M. Matrix: Sparse and Dense Matrix Classes and Methods (2012).R package version 1.0-10. URL http://CRAN.R-project.org/package=Matrix. Date of access: 12/11/2013.
- Seidman S. B. Network structure and minimum degree. Soc Networks 5, 269–287 (1983).
- Costenbader E. & Valente T. W. The stability of centrality measures when networks are sampled. Soc Networks 25, 283–307 (2003).
- Ghoshal G. & Barabsi A. L. Ranking stability and super-stable nodes in complex networks. Nat Commun 2, 394 (2011). [PubMed]
- Adiga A., Kumar A. & Vullikanti S. How robust is the core of a network? In [Blockeel, H., Kersting, K. Nijssen, S. and Zelezný, F. (ed.)] [541–556] ECML/PKDD, Springer (2013).
- Lloyd A. L. & May R. M. Epidemiology. How viruses spread among computers and people. Science292, 1316–1317 (2001). [PubMed]
- Newman M. E. J. Spread of epidemic disease on networks. Phys Rev E Stat Nonlin Soft Matter Phys66, 016128 (2002). [PubMed]
- Wilkinson R. R. & Sharkey K. J. An exact relationship between invasion probability and endemic prevalence for Markovian SIS dynamics on networks. PLoS One 8, e69028 (2013). [PMC free article][PubMed]
- Volz E. SIR dynamics in random networks with heterogeneous connectivity. J Math Biol 5, 293–310 (2008). [PubMed]
- Bressan M. & Peserico E. Choose the damping, choose the ranking? JDA 8, 199–213 (2010).
- Son S.-W., Christensen C., Grassberger P. & Paczuski M. Pagerank and rank-reversal dependence on the damping factor. Phys Rev E Stat Nonlin Soft Matter Phys 86, 066104 (2012). [PubMed]
- Leskovec J., Adamic L. A. & Huberman B. A. The dynamics of viral marketing. ACM Trans. Web 1 Article 5 (2007).
- Leskovec J., Lang K. J., Dasgupta A. & Mahoney M. W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Inter Math 6, 29–123 (2009).
- Viswanath B., Mislove A., Cha M. & Gummadi K. P. On the evolution of user interaction in Facebook. In: Proc 2nd ACM SIGCOMM Workshop on Social Networks (WOSN'09) (2009).
- Chung F. & Lu L. Connected components in random graphs with given expected degree sequences. Ann Comb 6, 125–145 (2002).
- Boguñá M., Pastor-Satorras R., Díaz-Guilera A. & Arenas A. Models of social networks based on social distance attachment. Phys Rev E Stat Nonlin Soft Matter Phys 70, 056122 (2004). [PubMed]
- Leskovec J., Kleinberg J. & Faloutsos C. Graphs over time: Densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD '05, 177–187 (ACM, New York, NY, USA, 2005). URL http://doi.acm.org/10.1145/1081870.1081893.
- Yang J. & Leskovec J. Defining and evaluating network communities based on ground-truth. In: Proc ACM SIGKDD Workshop on Mining Data Semantics, MDS '12, 3:1–3:8 (ACM, New YorkNY, USA, 2012).
- Guimerà R., Danon L., Díaz-Guilera A., Giralt F. & Arenas A. Self-similar community structure in a network of human interactions. Phys Rev E Stat Nonlin Soft Matter Phys 68, 065103 (2003).[PubMed]
- Cho E., Myers S. A. & Leskovec J. Friendship and mobility: User movement in location-based social networks. In: Proc 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '11, 1082–1090 (ACM, New YorkNY, USA, 2011).
- Richardson M., Agrawal R. & Domingos P. Trust management for the semantic web. In Fensel, D., Sycara, K. & Mylopoulos, J. (eds.) The Semantic Web - ISWC 2003, vol. 2870 of Lecture Notes in Computer Science, 351–368 (Springer Berlin/Heidelberg, 2003).
- Leskovec J., Huttenlocher D. & Kleinberg J. Signed networks in social media. In: Proc SIGCHI Conference on Human Factors in Computing Systems, CHI '10, 1361–1370 (ACM, New YorkNY, USA, 2010).
- Albert R., Jeong H. & Barabási A. Internet: Diameter of the world-wide web. Nature 401, 130–131 (1999).
