La comprensión de la influencia de todos los nodos en una red
Glenn Lawyer - Nature
Scientific Reports 5, Article number: 8665 (2015)
doi:10.1038/srep08665
Resumen
Medidas de centralidad, como el grado, k-shell, o centralidad de valores propios pueden identificar los nodos más influyentes de la red, pero rara vez son útilmente precisos para cuantificar el poder difusión de la gran mayoría de los nodos que no son muy influyentes. El poder difusión de todos los nodos de la red se explica mejor por considerar, desde una perspectiva epidemiológica continua en el tiempo, la distribución de la fuerza de la infección por cada nodo genera. El, la fuerza esperada métrica resultante, cuantifica con precisión nodo de difusión de poder bajo todos los modelos epidemiológicos primarios a través de una amplia gama de redes de contactos humanos arquetípicos. Cuando el poder nodo es baja, la influencia es una función del grado vecino. A medida que aumenta de poder, propio grado de un nodo se vuelve más importante. La fuerza de esta relación es modulada por estructura de red, siendo más pronunciado en, redes densas estrechas típicas de las redes sociales y el debilitamiento de las redes más amplias, más flexibles de asociación, como Internet. La fuerza esperada se puede calcular de forma independiente para los nodos individuales, por lo que es aplicable para las redes cuyos matriz de adyacencia es dinámica, no bien especificado, o abrumadoramente grande.Introducción
Las redes han convertido en el enfoque premier a describir los procesos de difusión, tales como epidemias o transferencia de información porque expresan la heterogeneidad de las interacciones característicos de muchos actividades humanas. Treinta años de innovación han perfeccionado nuestra capacidad para identificar los nodos que son de gran influencia en el resultado de casi cualquier proceso de difusión en una red dada a través de características como centralidad de intermediación, centralidad de valor propio, grado o k-shell. Sin embargo, los nodos altamente influyentes son raras, por definición, y las medidas que acabamos de mencionar no son informativos para la gran mayoría de los nodos de la red. Estas medidas de centralidad única rango nodos y no están diseñados para cuantificar la potencia de difusión. Mientras que la clasificación se identifican con precisión los pocos nodos altamente influyentes, pueden subestimar considerablemente el poder de difusión de nodos que no son centrales (hub). Tampoco estas clasificaciones incorporan explícitamente la dinámica de procesos de propagación. Esto deja abierta la cuestión de la cuantificación de la energía difusión de los mucho más numerosos nodos no muy influyentes, y de hecho la comprensión de la naturaleza del nodo de difusión propio poder. Como nodos altamente influyentes sólo en raras ocasiones se originan difundir los procesos, ya sean enfermedades patógenas, ideas innovadoras o conversaciones, hay una profunda hambre intelectual y la utilidad práctica de medir y comprender el poder difusión de cada nodo individual en una red con precisión.La potencia la difusión de un nodo es la fuerza con la que se puede empujar un proceso que se extiende al resto de la red. Esta definición puede hacerse más precisa con referencia a los modelos epidemiológicos comunes de propagación. En un proceso de difusión susceptible de ser infectados (SI) sin recuperación, que alcanza inevitablemente todo el componente conectado de la red, la potencia de propagación de la semilla nodo predice el retardo antes de la mitad (o alguna otra gran porcentaje de) se alcanza la red. En un proceso con recuperación ya sea a la susceptible (SIS) o inmunes (SIR) del estado, la difusión de la energía se correlaciona con la probabilidad de que un nodo puede sembrar una epidemia dado que la relación de la velocidad de transmisión por contacto a la tasa de recuperación permite , pero no garantiza, una epidemia. Cuando esta relación supera el rango crítico, la dinámica se acercan al sistema SI como un caso límite.
Recientemente se han propuesto varios enfoques para la cuantificación de la potencia de difusión de todos los nodos, incluyendo el accesibilidad, la influencia dinámico, y el impacto. Estos se extienden enfoques anteriores para medir la centralidad incorporando explícitamente la dinámica de propagación. La accesibilidad es una forma modificada de grado jerárquico que controla tanto las probabilidades de transmisión y la diversidad de los sectores de una longitud fija determinada. La influencia dinámica, como la centralidad valor propio, es la proporción de infinito paseos 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 a converger a un estado constante no nulo. Las sumas de impacto, sobre longitudes crecientes pie, la probabilidad de transmisión al nodo final de la caminata y que el nodo de extremo no se ha visitado previamente por un senderos más corto. Estas nuevas métricas de potencia de propagación se han demostrado para ser distinto de medidas de centralidad anterior y más altamente correlacionado con resultados de epidemia. Sin embargo, conservan el fundamento común de los enfoques más habituales a la centralidad, el conteo de paseos por la red. Como los paseos se cuentan utilizando potencias de la matriz de adyacencia, propagación se observa sólo en tiempo discreto.
La epidemiología, en cambio, estudia la dinámica de tiempo continuo de la fuerza de la infección (FOI), definida como la tasa actual en la que los nodos susceptibles son cada infectado. En los modelos de red, el FoI es directamente proporcional al número actual de aristas entre los nodos infectados y susceptibles. La distinción fundamental entre FoI y paseos es que el FoI se determina por el número de enlaces infectados susceptibles, independientemente de su distancia desde el nodo de la semilla. La distinción fundamental entre continuo- y de tiempo discreto es que continua en el tiempo permite la resolución a las dos primeras transmisiones, un nivel no se expresa fácilmente en un marco de tiempo discreto, donde pueden ocurrir múltiples transmisiones en cada paso de tiempo. La distinción es agudo, como el número de eventos por paso de tiempo crece a un ritmo de doble exponencial de red libre de escala, el tipo de red más representativo de estructuras humanas y tal vez incluso en su vida misma.
La perspectiva epidemiológica de tiempo continuo sugiere que la difusión de nodo de potencia se puede cuantificar con precisión resumiendo apropiadamente la distribución del número de aristas susceptibles infectadas después de un pequeño número de eventos de transmisión derivados de un nodo de semilla en una red de otro modo totalmente susceptible; es decir, por el FoI esperada generada por ese nodo. Estamos aquí proponemos una medida de este tipo, llamada la fuerza esperada (ExF), y mostramos que supera a la accesibilidad, k-shell, y centralidad valor propio en la predicción de los resultados de epidemia en el SI, SIS y SIR procesos de difusión, tanto en discrete- y continua -hora. La base de la estructura local de barrio: el ExF es aplicable incluso cuando la matriz de adyacencia completa es desconocido o inherentemente incognoscible. La métrica se extiende naturalmente a las redes ponderados y dirigidas. Lo más importante, la fuerza esperada es capaz de iluminar los factores responsables de potencia nodo de difusión.
Definición de la Fuerza Esperada
La fuerza esperada es una propiedad nodo derivado de topología de red local, independiente del resto de la red o cualquier proceso de difusión específico. Se formalmente se define como sigue. Considere una red con un solo nodo i infectado y todos los nodos restantes susceptibles. Enumerar todos los grupos posibles 1, ..., J de nodos infectados después de los eventos de transmisión de x, suponiendo que no hay recuperación (Ver Figura 1). En términos generales, x = 2 es suficiente y asumido por el resto de este manuscrito. De ahí J incluye todas las combinaciones posibles de i y dos nodos en la distancia uno del yo, y más un nodo a una distancia uno y uno a una distancia de dos. La enumeración es sobre todas las posibles ordenaciones 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 enlace, cuatro grupos. Después de dos transmisiones sin recuperación, la FoI de un proceso de difusión sembraron desde el nodo i es una variable aleatoria discreta teniendo un valor en (d1, …, dJ), lo que permite la constante de proporcionalidad igual a la velocidad de transmisión del proceso. La fuerza esperada de la infección se puede aproximar por la entropía del dj después de la normalización
donde i refiere al nodo semilla un
Esta red estará en uno de los ocho estados posibles después de dos transmisiones desde el nodo de la semilla (rojo). Dos estados se ilustran, donde la semilla se ha transmitido a los dos nodos de naranja a lo largo de los enlaces negros sólidos. Cada estado tiene un número asociado de (naranja discontinua) enlaces de nodos susceptibles (azules), el grado de clúster. Unidos que contienen dos vecinos de la semilla (panel A) se pueden formar de dos maneras o, si son parte de un triángulo, de cuatro maneras. Los ocho estados de red asociados con la semilla relevancia que el nodo en la foto de trece posibles agrupaciones de transmisión. La fuerza esperada de un nodo semilla es la entropía de la distribución del (normalizada) grado clúster sobre toda (aquí 13) posibles agrupaciones de transmisión.
Se necesita la entropía para generar el valor esperado debido a la variabilidad extrema en la forma, el número de modos, y el número de términos en las distribuciones de dj para diferentes nodos de semillas. Redes complejas tienen grado distribuciones libres de escala. Los momentos de las distribuciones libres de escala son divergentes, lo que implica que la distribución de dj no puede tener un valor medio en el sentido tradicional. La entropía es una herramienta estándar para domar distribuciones rebeldes debido a su estrecha relación con cumulante funciones generadoras, motivando el uso de la ecuación 1 para generar un valor cuasi-esperada del FoI. Una analogía suelta se puede hacer que el uso de la entropía en la física estadística para resumir el macroestado de un sistema (por ejemplo, la presión de un gas), basado en la distribución de sus microestados (las posiciones y momentums de moléculas en el gas). La analogía es que la presión es una combinación de la cantidad y el calor de las moléculas, así mismo, la fuerza esperada de un nodo es una combinación del número de posibles grupos de transmisión que puede formarse y la FoI generados por cada grupo. Una discusión en profundidad de la relación entre la entropía, cumulantes y física estadística se puede encontrar en review26 de Touchette.
Se recomienda ajustar x = 2, pero no es obligatorio. Investigaciones complementarias muestran que aumentar el número de transmisiones más allá de dos añade muy poca información al tiempo que aumenta el coste computacional (véase la nota complementaria 1), de acuerdo con otra propuesta métricas de difusión poder y consistente con la influencia en descomposición de las trayectorias más largas en los cálculos de el valor propio, subgrafo y centralidades relacionadas. En ciertos casos, sin embargo, puede ser deseable considerar más eventos de transmisión. Por ejemplo, un nodo en el extremo de una cadena de longitud dos sólo puede formar un clúster transmisión de tamaño dos, por lo tanto, su fuerza esperada es cero. La comparación de dos tales nodos requiere ajuste de x = 3, en cuyo caso un subíndice se puede utilizar para mayor claridad (por ejemplo ExF3).
Una modificación puede ser el fin de que los procesos de SIS / SIR, inspirados en lo siguiente. Imagine un nodo con grado uno conectado a un concentrador. Mientras que un nodo tal tendrá una fuerza esperada alta, su oportunidad de hacer realidad esta fuerza depende enteramente de la transmisión al cubo antes de la recuperación. Estos nodos son comunes en densas redes sociales. Por ejemplo, el 84% de los 225K nodos en un red de correo electrónico institución de la UE tienen grado una. En tales redes, puede ser útil para explicar la dependencia de la transmisión inicial multiplicando el ExF por el registro de grado del nodo simiente después de primero reescalado grado de la semilla por algún factor α> 1.
El cambio de escala está motivada en que el registro de uno es cero, y el exfm es más informativo en redes en las que muchos nodos tienen un grado una. El factor de cambio de escala debe ser mayor que uno, y también debe ser pequeña para evitar dominar la influencia del grado. En el resto de este manuscrito, usamos α = 2, el menor entero que satisface estos criterios. Nota complementaria 2 muestra que el cálculo de la exfm para α van 1,0001-16 no altera sustancialmente la métrica, como todas las variaciones muestran correlaciones superiores a 0,99 a exfm calcula con α = 2.
El cálculo directo de la fuerza esperada tiene complejidad temporal
, donde n1 y n2 son el número de vecinos en la distancia de uno y dos de la semilla. Es difícil comparar analíticamente una complejidad de tiempo calculado 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 únicamente en la información local, se puede calcular de una manera masiva en paralelo o sólo calcula en nodos de interés. También permite que los cálculos significativos (parciales), incluso en los gráficos masivos, es decir, aquellos cuyo tamaño abruma la memoria del ordenador. Sin embargo, una comparación de tiempos de ejecución se requiere de indicadores existentes. Nos referencia la mediana del tiempo de ejecución más de cincuenta redes Pareto de 1.000 nodos de todas las medidas discutidas aquí. El tiempo de ejecución de cada red se mide como la mediana del tiempo de cálculo más de diez carreras en esa red, con el tiempo de cálculo se mide a con una precisión de sub-microsegundo. El cálculo del ExF para todos los nodos no-hub tarda 0,16 segundos. El k-shell se calcula en 2% de ese tiempo (0.003 segundos), y la centralidad valor propio en el 20% de ese tiempo (0.03 segundos). Cálculo de la accesibilidad tiene varios cientos de veces más. La evaluación comparativa se repite con el mismo protocolo de nodo 10.000 redes de Pareto. Los incrementos en el tiempo de funcionamiento de la concha k (6x), centralidad valor propio (9x), y se espera la fuerza (16x) tienen correspondencia aproximadamente lineal con el aumento de diez veces en el número de nodos de la red. Recordemos que la complejidad del tiempo probada para el k-shell y la hora prevista para la centralidad de valores propios son ambos O (| V | + | E |), es decir, lineal. Como era de esperar, la accesibilidad no escala bien, con un incremento de diez veces en el tamaño de la red que lleva a un aumento de 265 veces en la mediana de tiempo de ejecución. Recordemos que se calcula tomando los poderes de la matriz de adyacencia, es decir, algo peor que O (| V | 2.4). Benchmarking se llevó a cabo en el entorno de programación R29 se ejecuta en un ordenador portátil de los productos básicos. K-shell y valores propios cálculos se calculan a través de las funciones estándar de la paquete IGRAPH. La accesibilidad se calcula en el código R29 nativa utilizando la multiplicación matriz dispersa desde el paquete Matrix 1,0-1.031. La fuerza esperada se calcula de código C a través de una interfaz R.Un ejemplo de código que proporciona una implementación de la fuerza esperada está disponible en https://github.com/glennlawyer/ExpectedForce.
La correlación con los resultados de epidemia
Medimos las correlaciones entre los resultados de la fuerza y epidémicas esperados en cinco familias de redes simuladas elegidos de tal manera que sus densidades y distribuciones de grado abarcan una amplia gama de estructuras de contacto humano, que se enumeran en la Tabla 1. El cien redes aleatorias de 1.000 nodos se generan en cada familia . Además la comparación se realiza mediante un conjunto de veinticuatro redes del mundo real que van desde 1,133 a 855,800 nodos, como se indica en la Tabla 2. Los resultados de epidemia son el tiempo a la mitad la cobertura de los procesos del SI y el potencial epidémico para procesos SIS y SIR. Estos se observan mediante la simulación de múltiples epidemias tanto en tiempo continuo y discreto a partir de un número de nodos de semillas en cada red. Las correlaciones se miden entre estos resultados y la fuerza esperada, exfm, la accesibilidad, la centralidad de valores propios, y el k-shell de los nodos de semillas. Motivaciones para estas elecciones y detalles adicionales se dan en los métodos.Tabla 1: Simulación de las familias de la red. El diámetro medio, media densidad gráfica, y empírica media 65% Gama cuantil del mayor valor propio de las diferentes familias de la red. Pareto y Amazonas redes co-compra tienen una gran estructura, sueltos y poco valor propio, lo que sugiere la susceptibilidad menos inherente a las epidemias que las redes de colaboración más pequeñas y más densas; Mapa de Internet de Google se encuentra en el medio. Los medios y las desviaciones estándar se calculan más de 100 redes simuladas con 1.000 nodos
| diámetro | densidad | 65% cuantil | |
|---|---|---|---|
| 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, 90a percentil diámetro efectivo, y la densidad de las redes reales. Redes fueron descargados de la Stanford Large Red Collection (SNAP), la colección de Alex Arena (AA), y el Instituto Max Planck para la página web Software Systems (MPI), que a su vez créditos de la publicación citada por la red
| nodes | diameter | density | source | |
|---|---|---|---|---|
| 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 predictivo de todos los resultados de epidemia en todas las redes analizadas, simulado y real. La media de correlación con los resultados del proceso de la IS es 83% en simulación y el 74% en las redes reales. Para los procesos con la recuperación, la correlación media es del 91% sobre simulado y el 82% en las redes reales. Las desviaciones estándar en los cien redes simuladas en cada familia son típicamente 0,02-0,03. Los 95% límites de confianza en las redes reales están en el mismo rango. En todos los casos la ExF (o exfm) supera significativamente la accesibilidad y la centralidad valor propio (diferencia en correlaciones medias mayores que la desviación estándar de la media más alta). Por lo general supera a la k-shell, superando significativamente en 82 casos, mostrando un rendimiento equivalente en 11 casos (diferencia en correlaciones medias menores que la desviación estándar de la media más alta), y el rendimiento significativamente inferior en 6 casos (redes de Internet simulada SIS- C, SIR-C, SIR-D; redes Astrofísica simulados SIR-D, las redes de Facebook simulados SIR-D, "email-EUAll" red de SI). El rendimiento de la k-shell era sorprendentemente fuerte, dado que los dos estudios previos por parte de grupos independientes han observado bastante pobre desempeño de este indicador. 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 de tabla en la tabla complementaria 5. Del mismo modo, las correlaciones medidos y sus errores estándar para todas las redes reales se muestran en la Figura 3, dadas en forma de tabla en los cuadros suplementarios 6, 7 y 8, y se representan de forma individual en las figuras complementarias 16.
Figura 2: Correlación de propagación de las métricas de potencia a los resultados epidémicas en las redes simuladas.
Figuras de Violín muestran la distribución de valores de correlación observados para cada resultado proceso de difusión en cada familia red. La fuerza de lo esperado y exfm (tonos naranja) son consistentemente fuerte, con correlaciones medias superiores a 0,85 y pequeña variación. Las otras medidas (k-shell, centralidad valor propio, y de accesibilidad, tonos azules y verdes) muestran ambos valores medios más bajos y mayor varianza, como se ve en la posición y la propagación vertical de sus violines. Cada violín resume las correlaciones calculadas en 100 redes simuladas. Procesos Difusión (eje x) se sufijo para indicar simulaciones en continuo (C) o discreta (-D) tiempo. El resultado epidemia para los procesos de SI es el tiempo hasta que se infecta medio de la red. Para SIS y SIR procesa es la probabilidad de que se observa una epidemia.
Figura 3: Correlación de difundir mediciones de potencia a los resultados de epidemia en las redes reales.
Gráficas de puntos y barras de error muestran la correlación observada y el intervalo de confianza del 95% entre cada medida y la difusión de los resultados del proceso en las 24 redes reales. La fuerza esperada y exfm (tonos naranja) muestran un desempeño sólido, superando constantemente las otras métricas (k-shell, centralidad valor propio, y de accesibilidad cuando computados, tonos azul-verde). El resultado epidemia para los procesos de SI es el tiempo hasta que se infecta medio de la red. Para SIS y SIR procesa es la probabilidad de que se observa una epidemia. El sufijo "-D" indica difundir procesos simulados en tiempo discreto. Paneles individuales se dan como cifras separadas (más grandes) de las figuras complementarias 1-6.
Poder predictivo del vigor se espera es robusto a la variación en la estructura de red. La teoría detrás de la exfm sugiere que el ExF podría perder rendimiento para SIS / SIR procesa en las redes más densas, pero significaría correlación para procesos SIS tiempo continuo apenas cambió entre las redes sueltas Pareto / Amazonas (0,93 / 0,95) y la densa Astrofísica / Facebook redes (0,92 / 0,90). Como era de esperar, el poder predictivo de la exfm mejora en las redes más densas (media correlaciones: Pareto / Amazon 0.89 / 0.92, Astrofísica / Facebook 0.94 / 0.95). Un análisis previo que observa malos resultados similares: La precisión de la métrica de la accesibilidad, por el contrario, se derrumba para todos los procesos de difusión en las redes densas (Pareto / Amazon 0.74 / 0.90, Astrofísica / Facebook 0.28 / 0.20. La correlación sobre todos los procesos de extensión media) para la accesibilidad en las redes densas concluyeron que los procesos de difusión sembradas de nodos con baja accesibilidad no son capaces de entrar en el phase18 epidemia. Nuestros resultados muestran que esto no es el caso, ya que estos nodos tienen un pequeño potencial epidémico todavía observable que la fuerza esperada es capaz de capturar y cuantificar. El rendimiento de la k-shell y la centralidad de valores propios también está fuertemente influenciada por la estructura de la red. Para los procesos SIS / SIR, ambos mostraron mayor media y la drástica reducción de la varianza en las redes más densas. En un contraste interesante, el poder predictivo del k-shell para los procesos del SI se reduce en las redes más densas. El desempeño de la centralidad de valores propios también varía según el proceso de difusión, mostrando su mejor rendimiento en tiempo discreto SIS modelos- aunque de nuevo esta variación es modulada por densidad de la red. Otros dos grupos independientes han observado que las relaciones entre el ranking de centralidad y resultados epidémicas están fuertemente influenciadas por la estructura de la red y los parámetros de los procesos de difusión, lo que lleva a los autores de ref. 9 a la conclusión de que estas medidas subestiman gravemente el impacto epidemia de nodos estructuralmente periféricos.
Grafos ponderados
La fuerza esperada generaliza a grafos con enlaces ponderados, donde asumimos el peso del enlace corresponden a las probabilidades de transmisión por punta. Utilice estos pesos para calcular la probabilidad de cada forma en que podría ocurrir cada grupo, y volver a definir el grado de clúster como la suma de todos los pesos de vanguardia hacia fuera de ese grupo. La extensión de grafos dirigidos también es sencillo; limitar la enumeración de enlaces de ataque de un infectado a un nodo susceptible.Probamos esta generalización calculando la fuerza esperada ponderado y no ponderado de 1.000 redes de nodos con Pareto (1,2.3) distribuciones de grado y pesos de las aristas elegidos de acuerdo con una de las siguientes tres distribuciones: distribuida uniformemente entre uno y tres, distribuidos uniformemente entre uno y diez, y exponencialmente distribuido con tasa unitaria, pesos redondean al número entero más cercano. Se simularon Cincuenta redes para cada distribución de pesos de las aristas. La correlación entre la ExF ponderado y no ponderado fue mayor que 0,99 para todas las distribuciones de ponderación de los enlaces de la red probadas. Como era de esperar de la estrecha correlación, la ExF ponderado y no ponderado no mostró ninguna diferencia significativa en la capacidad de predicción, que se mantuvo alta. Correlaciones observadas entre el nodo espera la fuerza y potencial epidémico en los procesos de SIS en tiempo discreto fueron 0,88 / 0,89 ± 0,03 (no ponderado / ponderada ExF) con arreglo al régimen uniforme-3, 0.83 / 0.04 ± 0.03 bajo el esquema de 10 uniformes, 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 epidémicas con alta precisión sobre una amplia gama de estructuras de red y los procesos de ensanchamiento. La baja variación en las correlaciones observadas en múltiples modelos de red y epidémicas simulados muestra que la medida es robusto, al igual que los límites de confianza ajustados en las redes del mundo real. ¿Cuál es, entonces, qué nos dice sobre la naturaleza del nodo de difusión de poder? La definición de la fuerza esperada implica que la difusión de potencia se determina por tanto el grado del nodo y el grado de sus vecinos, y que la influencia relativa de estos dos factores es diferente para los nodos de baja frente a la difusión de alta potencia. Nodos débiles ganar lo 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 acentúan por la densidad de la red.Este es un resultado de la combinatoria detrás de la enumeración sobre agrupaciones de transmisión. El número de rutas con un borde (p1) contribuye cuadráticamente con el número de racimos de transmisión, mientras que el número de caminos de dos de borde (p2) contriutes linealmente, ya J = p1 * (p1 - 1) + p2. Grado de nodo es exactamente p1. Grado Vecino es en la mayoría de p2. Nodos más débiles tienden a tener menor grado, por lo tanto, el grado vecino contribuye en mayor medida a su fuerza esperada. La influencia de la densidad de la red proceden en parte de la sensibilidad de la ExF de motivos de la red, tales como triángulos y cuadrados. Cada triángulo se traza por dos caminos con dos bordes, aumentando la proporción de p2 asociados con el grado de nodo. Más importante aún, el ExF es la entropía de la conectividad en adelante de cada grupo de transmisión. Un triángulo genera cuatro de estos grupos, cada uno de los cuales tiene el grado de clúster idénticos. Del mismo modo, cada cuadrado representa dos grupos. Estos motivos de la red, que son más comunes hacia los núcleos de las redes densas y reducir la disparidad de la distribución de grado de clúster que aumenta la entropía. Los combinatoria se complican cuando el recuento se basa en más de dos transmisiones, pero estos patrones generales permanecen. Estas relaciones pueden ser vistos por el trazado de ExF contra las sumas de los grados de los nodos en el aumento de la distancia geodésica de la semilla (Figura 4, que complementa el cuadro 3).
Figura 4: Extensión de la energía es un factor de primer y segundo grado la orden de un nodo.
Trazado de la fuerza esperada (eje x) frente a grado nodo (naranja), la suma del grado de todos los vecinos (Azules), y la suma del grado de todos los vecinos en la distancia 2 (verde) muestra que para los nodos con baja ExF, grado del vecino tiene una fuerte correlación con ExF, mientras que para los nodos con alta ExF su propio grado está más estrechamente correlacionados. El resultado se acentúa en las redes de colaboración más densos en comparación con las redes de Pareto más difusos. La correlación entre ExF y el grado vecino es 0,94 ± 0,01 en las redes de colaboración, y se reduce a 0,84 ± 0,02 en las redes de Pareto (media tomado más de 50 redes; Ver cuadro complementario 3 para las correlaciones más de todas las estructuras de la red).
El enfoque adoptado por la fuerza esperada es fundamentalmente diferente de la adoptada por la mayoría de las medidas de centralidad. Medidas de centralidad normalmente establecidos para producir una clasificación que identifica los nodos más influyentes en la red, bajo el supuesto de que los nodos altamente influyentes son aquellos con la suma máxima de algún tipo de paseo. La elección del tipo adecuado, escalamiento, y la duración de las caminatas contiene supuestos implícitos en relación con los flujos de red, la estructura de la cohesión, y / o otras características topológicas de la red. El k-shell es una pequeña excepción, ya que inicialmente estaba destinado a precipitar las regiones más cohesivas de la red en lugar de para clasificar explícitamente nodos dentro de las regiones de cohesión, sin embargo, ahora se reconoce como una de las mejores medidas de centralidad para la identificación de una red de difusores más influyente. Difundir las métricas de poder generalizar el paseo contando marco al incluir explícitamente las probabilidades de transmisión al escalar los paseos. La cuestión no se plantea es si el tipo, escala, y las longitudes de los sectores que mejor se adapte a la identificación de los nodos más importantes se aplica igualmente bien con el resto de la red. En la medida en que la elección óptima de los factores depende de la topología de red, entonces la diferencia en la topología entre el núcleo y la periferia sugiere que las opciones muy apropiadas para el núcleo son menos apropiados para el resto de la red.
Tanto la combinatoria detrás de la fuerza esperada y el paseo contando detrás medidas más centralidad de acuerdo en que los nodos influyentes son aquellos que combinan alto grado con una preponderancia de vecinos influyentes. El ExF tiene alta correlación rango tanto con la centralidad de valores propios y de la cáscara de k (0,62-0,92 a través de las familias de la red simulada, véase la nota complementaria 3). Asimismo, el ExF tiene 60-90% de acuerdo con la centralidad valor propio en el diez nodos de red y 100% del acuerdo superior con el k-shell. La diferencia entre el conteo de pie y la fuerza esperada es que la fuerza esperada adopta la influencia relativa de los diferentes sectores y caminar largos basados en conectividad local, mientras que los enfoques basados en funciones de la matriz de adyacencia aplican un protocolo fijo. La centralidad de valores propios es el grado del nodo ponderada, donde los pesos son la importancia de los vecinos. Pero la centralidad valor propio es estrictamente una medida global, incapaz de distinguir las variaciones más sutiles en la estructura local. El k-shell erosiona grado nodo para que coincida con el número de vecinos con grado similar. Desde esta descarta restante información sobre el grado individual de nodos dentro de una carcasa común, la exactitud de sus predicciones está fuertemente influenciado por el número de conchas en la red. La accesibilidad combina nodo y el grado vecino en una medida del número de nodos susceptibles de ser alcanzado por los sectores de una longitud dada. Pero este enfoque tiene dificultades cuantificar nodos en redes de diámetro densos, pequeñas, que acentúan las diferencias entre el núcleo y la topología periférica.
La fuerza esperada ofrece ventajas adicionales sobre la difusión medidas de potencia y de centralidad existentes en que su cálculo sólo depende de la topología local. Esto permite que los resultados de epidemia en toda la red para predecir con gran precisión incluso cuando se conoce sólo una pequeña porción de la red. Es raro que la estructura completa de una red real para ser totalmente conocido; normalmente la estructura de red se infiere de observaciones indirectas, incompletas, ya menudo sesgadas. 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 centralidad valor propio fluctúan dependiendo de que se muestrean nodos. Tanto el Pagerank y el k-shell son muy sensibles a pertubaciones en topología de la red, por lo que poco fiable para sistemas incompletos o ruidosos.
La confianza en un vecindario local es consistente con la teoría establecida mostrando que topológica de contenido de información cae rápidamente con la distancia. Bonacich demostrada en 1987 que la centralidad valor propio se puede expresar en términos de sumas sobre los ámbitos de longitud k, k = 1 ... ∞, estableciendo que la influencia de los sectores debe decaer, al menos de manera exponencial en k para garantizar convergencia. Un trabajo más reciente muestra que casi todas las medidas de centralidad, incluidos los basados en resolventes matriz, así mismo se puede expresar como sumas infinitas más bases por bolas, y que las tasas de decaimiento exponencial más rápido que a menudo son motivados. La caída de la información también puede ser mostrado por el siguiente ejemplo. Considere una cadena lineal larga de nodos que conecta finalmente a un concentrador de red. Vamos β sea la relación de transmisión / recuperación en un proceso con recuperación y Delta I de la distancia desde el nodo i-ésimo de la cadena al concentrador. Si el proceso de difusión alcanza el centro, una epidemia es casi seguro. La probabilidad de que esto ocurra es en el mejor. Para β <0,1, esta probabilidad es estimable a tres de cuatro cifras decimales utilizando información solamente local. De manera más general, ya que la propagación epidémica es casi instantánea en las redes libres de escala, la expectativa es que el tiempo de paso que tiene un proceso fuera de la vecindad local de su origen lo lleva a la mayoría de la red.
La confianza en una red local, sin embargo, conduce a una debilidad en la fuerza esperada. Una red puede contener grandes comunidades pero dispares. Aquí, un nodo que actúa como un puente entre dos comunidades podría ser capaz de propagarse a un proceso para toda la red con más fuerza que un nodo lejos del puente, incluso cuando el segundo nodo tiene más (local) de potencia difusión que el nodo de puenteo. Carácter local del vigor se esperaba hace ciegos a estas restricciones topológicas más grandes en expansión.
Este trabajo define el resultado epidemia en el SIS / SIR procesa como la probabilidad de que se produzca una epidemia. Esto está en contraste con la medida utilizada normalmente, el número medio de nodos infectados (es decir, refs. 6, 8, 9, 11, 17, 18, 37). No estamos convencidos de que la media es un buen resumen estadístico. En más de 20.000 procesos de tiempo continuo simulado SIS difusión, no hay procesos que se extinguieron llegaron a más de 20 nudos, mientras que los procesos que no se extinguen llegaron a la mayoría de la red. Se ha argumentado que tal bifurcación en los resultados es predicha por la teoría. Dado que la distribución del número de nodos infectados se caracteriza por dos modos bien separados, la media se ve mejor como una estimación indirecta de la probabilidad de que el modo superior. Es esta posibilidad la que medimos directamente como el potencial epidemia.
La fuerza esperada predice resultados de epidemia de características locales de los nodos específicos en una red específica, con la única referencia de pasada a la naturaleza y los parámetros del proceso de difusión. Trabajo seminal ha abordado la cuestión desde el otro lado. Teniendo en cuenta los parámetros de un proceso de difusión de SIR y una clase de redes caracterizadas por su grado de distribución, soluciones exactas para valores típicos de una serie de resultados epidémicas están disponibles, y su evolución en el tiempo pueden expresarse como ecuaciones diferenciales ordinarias pareadas. Nodo de difusión de potencia puede ser pensado como explicando que parte de la varianza en torno a estos valores típicos que se debe a la elección de nodo de semilla.
La fuerza esperada está fuertemente correlacionada con el resultado epidemia, superando las métricas existentes de nodo de poder difundir y centralidad. La medida depende sólo de topología de la red local, permitiendo su uso en la dinámica así como las redes estáticas. Para la mayoría de los nodos, el determinante más importante de su poder de difusión es la suma del grado de sus vecinos. Como el poder nodo crece, también lo hace la importancia del propio grado del nodo. Esta relación se acentúa en las redes más densas.
