La topología de las redes ponderadas

La arquitectura de las redes ponderadas complejas

A. Barrat *, M. Barthélemy †, R. Pastor-Satorras ‡, y A. Vespignani *, §
afiliaciones de autor

Comunicado por Giorgio Parisi, Universidad de Roma, Roma, Italia, 8 de enero de 2004 (recibido para revisión el 29 de octubre de 2003)

PNAS

ResumenLas estructuras en red surgen en una amplia gama de contextos diferentes, tales como las infraestructuras tecnológicas y de transporte, los fenómenos sociales y los sistemas biológicos. Estos sistemas altamente interconectados han sido recientemente el foco de una gran atención que ha descubierto y caracterizado su complejidad topológica. Junto con una compleja estructura topológica, las redes reales muestran una gran heterogeneidad en la capacidad e intensidad de las conexiones. Sin embargo, estas características no se han considerado principalmente en estudios anteriores en los que los enlaces se representan normalmente como estados binarios, es decir, presentes o ausentes. Aquí estudiamos la red de colaboración científica y la red mundial de transporte aéreo, que son ejemplos representativos de sistemas sociales y de grandes infraestructuras, respectivamente. En ambos casos es posible asignar a cada enlace del grafo un peso proporcional a la intensidad o capacidad de las conexiones entre los diversos elementos de la red. Definimos métricas apropiadas que combinan observables ponderados y topológicos que nos permiten caracterizar las propiedades estadísticas complejas y la heterogeneidad de la resistencia real de enlaces y vértices. Esta información nos permite investigar las correlaciones entre las cantidades ponderadas y la estructura topológica subyacente de la red. Estos resultados proporcionan una mejor descripción de las jerarquías y principios organizativos en la base de la arquitectura de redes ponderadas.
Un gran número de sistemas naturales y artificiales se estructuran en forma de redes. Ejemplos típicos son los grandes sistemas de comunicación (Internet, red telefónica, World Wide Web), las infraestructuras de transporte (rutas ferroviarias y aéreas), los sistemas biológicos (redes de interacción de genes y / o proteínas) y una variedad de estructuras de interacción social -3). Las propiedades macroscópicas de estas redes han sido objeto de intensa actividad científica que ha puesto de manifiesto la aparición de una serie de características topológicas significativas. Específicamente, muchas de estas redes muestran la propiedad del mundo pequeño (4), lo que implica que la red tiene una distancia topológica media entre los distintos nodos que aumenta muy lentamente con el número de nodos (logarítmica o incluso más lenta), a pesar de mostrar un alto grado De interconexión local típica de los retículos más ordenados. Adicionalmente, varias de estas redes se caracterizan por una abundancia estadística de "hubs" con un número muy grande de conexiones k comparadas con el valor medio grado Formula. La evidencia empírica recogida a partir de datos reales indica que esta característica distintiva encuentra su caracterización estadística en presencia de distribuciones de grados libres de escala P (k), es decir, mostrando un comportamiento de potencia-ley P (k) ~ k -γ para un rango significativo De valores de k (5). Estas características topológicas resultan ser extremadamente relevantes porque tienen un fuerte impacto en la evaluación de las propiedades físicas de estas redes como su robustez o vulnerabilidad (6-9).
Si bien estas conclusiones por sí solas pueden proporcionar una visión para el análisis de amenazas y las decisiones de política, las redes se especifican no sólo por su topología, sino también por la dinámica de la información o el flujo de tráfico que tiene lugar en la estructura. En particular, la heterogeneidad en la intensidad de las conexiones puede ser muy importante en la comprensión de los sistemas sociales. Análogamente, la cantidad de tráfico que caracteriza las conexiones en los sistemas de comunicación y las grandes infraestructuras de transporte es fundamental para una descripción completa de estas redes.
Motivados por estas observaciones, emprendemos en este trabajo el análisis estadístico de redes complejas cuyos enlaces se han asignado a un peso dado (el flujo o la intensidad) y por lo tanto pueden describirse generalmente en términos de grafos ponderados (10, 11). Trabajando con dos ejemplos típicos de este tipo de red, introducimos algunas métricas que combinan de forma natural tanto la topología de las conexiones como el peso que se les asigna. Estas cantidades proporcionan una caracterización general de las propiedades estadísticas heterogéneas de pesos e identifican definiciones alternativas de centralidad, cohesividad local y afinidad. Mediante mediciones apropiadas también es posible explotar la correlación entre los pesos y la estructura topológica del grafo, revelando la arquitectura compleja mostrada por redes ponderadas reales.

Datos de redes ponderadas

Para proceder al análisis general de las redes ponderadas complejas consideramos dos ejemplos específicos para los cuales es posible tener una caracterización completa de los enlaces entre los elementos de los sistemas, la red mundial de aeropuertos (WAN) y la red de colaboración científica SCN).

WAN. Analizamos la base de datos de la Asociación Internacional de Transporte Aéreo (www.iata.org) que contiene la lista mundial de pares de aeropuertos conectados por vuelos directos y el número de plazas disponibles en cualquier conexión para el año 2002. El grafo de transporte aéreo resultante comprende N = 3.880 vértices denota aeropuertos y E = 18.810 enlaces que representan la presencia de una conexión de vuelo directo. El grado medio de la red es  , mientras que el grado máximo es 318. La topología del grafo muestra tanto las propiedades del mundo pequeño como las sin escalas, como ya se observó en diferentes análisis de conjuntos de datos (12, 13). En particular, la longitud media de la trayectoria más corta, medida como el número medio de aristas que separa cualquier dos nodos de la red, muestra el valor Formula, muy pequeño comparado con el tamaño de la red N. La distribución del grado toma la forma P(k) = k -γ f(k/k x), donde γ ≅ 2.0 y f(k/k x) es una función de corte exponencial que encuentra su origen en restricciones físicas sobre el número máximo de conexiones que un solo aeropuerto puede manejar (3, 13 ). Por lo tanto, el gráfico de conexión al aeropuerto es un ejemplo claro de una red con una distribución heterogénea de grados, que muestra propiedades libres de escala en una amplia gama de valores de grado.

SCN. Consideramos la red de científicos que han escrito manuscritos enviados al Archivo de e-Print en relación con la física de la materia condensada (http://xxx.lanl.gov/archive/cond-mat) entre 1995 y 1998. Los científicos están identificados con nodos, Y existe una ventaja entre dos científicos si han coautorizado al menos un trabajo. La red conectada resultante tiene N = 12.722 nodos, con un grado medio (es decir, número medio de colaboradores ) y grado máximo 97. Las propiedades topológicas de esta red y otras redes similares de colaboraciones científicas han sido estudiadas en refs. 14-16.

Las propiedades de un grafo pueden ser expresadas por su matriz de adyacencia a ij, cuyos elementos toman el valor 1 si un enlace conecta el vértice i con el vértice j y 0 en caso contrario. Los datos contenidos en los conjuntos de datos anteriores permiten ir más allá de esta representación topológica definiendo un gráfico ponderado (10) que asigna un peso o valor que caracteriza cada enlace de conexión. En el caso de la WAN, el peso w ij de un enlace que une los aeropuertos iyj representa el número de asientos disponibles en los vuelos entre estos dos aeropuertos. La inspección de los pesos muestra que el número medio de asientos en ambas direcciones es idéntico w ij = w ji para una abrumadora mayoría de enlaces. En lo sucesivo trabajaremos con el gráfico simétrico no dirigido y evitaremos la complicación derivada de los desequilibrios de flujo. Se muestra un ejemplo del gráfico ponderado resultante en la Fig. 1. Es evidente que la definición anterior de pesos es una medida directa y objetiva del flujo de tráfico en la parte superior de la red.


Figura. 1.
Representación gráfica del grafo ponderado obtenido de los datos de la red aeroportuaria. Los principales aeropuertos de los Estados Unidos están conectados por enlaces que indican la presencia de un vuelo sin escalas en ambas direcciones cuyos pesos representan el número de asientos disponibles (millones / año).

Para el SCN seguimos la definición de peso introducida en refs. 14 y 15: La intensidad w ij  de la interacción entre dos colaboradores i y j se define como

Donde el índice p corre sobre todos los papeles, n p es el número de autores de papel p, y  es 1 si el autor i ha contribuido al papel p y 0 de lo contrario. Si bien cualquier definición de la intensidad de una conexión en las redes sociales depende de los elementos particulares elegidos para ser relevantes, la definición anterior parece ser más objetiva y representativa de la interacción científica: Es grande para los colaboradores que tienen muchos documentos en común, Al peso introducido por cualquier papel dado es inversamente proporcional al número de autores.

Centralidad y ponderaciones

Para tener en cuenta la información proporcionada por el grafo ponderado, identificaremos las cantidades apropiadas que caracterizan su estructura y organización a nivel estadístico. El análisis estadístico de los pesos w ij entre pares de vértices indica la presencia de distribuciones asimétricas hacia la derecha, ya señalando un alto nivel de heterogeneidad en el sistema tanto para la WAN como para el SCN como también se indica en refs. 12, 14 y 15. Sin embargo, se ha observado que los ponderadores de los enlaces individuales no proporcionan una imagen general de la complejidad de la red (11). Una medida más significativa de las propiedades de la red en términos de los pesos reales se obtiene extendiendo la definición del grado de vértice k i = Σj a ij en términos de la fuerza de vértice s i,, definida como

Esta cantidad mide la fuerza de los vértices en términos del peso total de sus conexiones. En el caso de la WAN, la intensidad de los vértices simplemente explica el tráfico total manejado por cada aeropuerto. Por el contrario, la fuerza es una medida de la productividad científica porque es igual al número total de publicaciones de cualquier científico dado, excluyendo las publicaciones de autor único. Esta cantidad es una medida natural de la importancia o centralidad de un vértice i en la red.

La identificación de los nodos más centrales del sistema es un problema importante en la caracterización de la red (17). La medida topológica más intuitiva de la centralidad viene dada por el grado: los nodos más conectados son más centrales. Sin embargo, más no es necesariamente mejor. De hecho, al considerar únicamente el grado de un nodo, hacemos caso omiso de que los nodos de grado pequeño pueden ser cruciales para conectar diferentes regiones de la red actuando como puentes. Para determinar cuantitativamente el papel de estos nodos, se ha definido la centralidad de intermediación (14, 15, 17, 18) como el número de trayectos más cortos entre pares de vértices que pasan a través de un vértice dado. Los nodos centrales son por lo tanto parte de los más cortos Dentro de la red que los nodos periféricos. Además, la centralidad de intermediación se utiliza a menudo en las redes de transporte para proporcionar una estimación del tráfico manejado por los vértices, suponiendo que el número de trayectos más cortos es una aproximación de orden cero a la frecuencia de uso de un nodo dado. De centralidad se basa sólo en elementos topológicos. Por lo tanto, es intuitivo considerar la definición alternativa de centralidad construida considerando la fuerza s i de los vértices como una definición más apropiada de la importancia de un vértice en redes ponderadas. Por ejemplo, en el caso de la WAN, esta cantidad proporciona el tráfico real que atraviesa el vértice i, y es natural estudiar cómo se compara y correlaciona con otras medidas topológicas de centralidad.

La distribución de probabilidad P(s) de que un vértice tiene fuerza s es pesada en ambas redes, y el comportamiento funcional presenta similitudes con la distribución de grados P(k) (ver Fig. 2). Una descripción funcional precisa de las distribuciones de cola pesada puede ser muy importante para entender la evolución de la red y será diferida para un análisis futuro. Este comportamiento no es inesperado porque es plausible que la fuerza s i aumente con el grado de vértice k i y, por lo tanto, la lenta cola decadente de P(s) deriva directamente de la muy lenta decadencia de la distribución de grados. Para arrojar más luz sobre la relación entre la fuerza y ​​el grado de los vértices, investigamos la dependencia de s i en k i. Encontramos que la fuerza media s(k) de vértices con grado k aumenta con el grado como

Fig.2. (A) Grado (inserción) y distribución de la fuerza en el SCN. El grado k corresponde al número de coautores de cada científico, y la fuerza s representa el número total de publicaciones del científico. Las distribuciones son de cola pesada incluso si no es posible distinguir una forma funcional definida. (B) Las mismas distribuciones para la WAN. El grado k (inserto) es el número de conexiones sin escalas a otros aeropuertos, y la fuerza s es el número total de pasajeros manejados por cualquier aeropuerto dado. En este caso, la distribución del grado puede ser aproximada por el comportamiento de la ley de potencia P(k) ∼ k -γ  con γ = 1.8 ± 0.2. La distribución de la fuerza tiene una pesada cola que se extiende más de cuatro órdenes de magnitud.

En ausencia de correlaciones entre el peso de los bordes y el grado de vértices, los pesos w ij  son en promedio independientes de i y j, por lo que podemos aproximar , donde  es el ponderador promedio en la red. De la ecuación 2 entonces tenemos . Es decir, la fuerza de un vértice es simplemente proporcional a su grado, dando un exponente β = 1, y las dos cantidades proporcionan por lo tanto la misma información sobre el sistema. En la Fig. 3 se presenta el comportamiento obtenido tanto para las redes ponderadas reales como para sus versiones aleatorias, generadas por una redistribución aleatoria de los pesos reales sobre la topología existente de la red. Para el SCN las curvas son muy similares y bien ajustadas por la fuerza de aproximación no correlacionada  . Curiosamente, este no es el caso de la WAN. La Fig. 3B muestra claramente un comportamiento muy diferente para el conjunto de datos reales y su versión aleatoria. En particular, el ajuste de potencia-ley para los datos reales da un exponente "anómalo" βWAN = 1,5 ± 0,1. Este valor implica que la resistencia de los vértices crece más rápidamente que su grado, es decir, el peso de los bordes que pertenecen a vértices altamente conectados tiende a tener un valor mayor que el correspondiente a una asignación aleatoria de pesos. Esta tendencia denota una fuerte correlación entre el peso y las propiedades topológicas en la WAN, donde cuanto más grande es un aeropuerto, más tráfico puede manejar.


Fig. 3. La fuerza media s (k) en función del grado k de los nudos. (A) En el SCN los datos reales son muy similares a los obtenidos en una red ponderada al azar. Sólo a valores k muy grandes es posible observar una ligera desviación del comportamiento lineal esperado. (B) En la WAN los datos reales siguen un comportamiento de ley de potencia con exponente β = 1,5 ± 0,1. Este valor denota correlaciones anómalas entre el tráfico manejado por un aeropuerto y el número de sus conexiones.

La huella dactilar de estas correlaciones también se observa en la dependencia del peso w ij en los grados de los nudos finales k i y k j. Como podemos ver en la Fig. 4, para la WAN el comportamiento del peso medio en función de los grados de punto final puede ser bien aproximado por una dependencia de la ley de potencia

Fig.4. Peso medio en función del grado de punto final. La línea continua corresponde a una fórmula de comportamiento potencia-ley, con exponente θ = 0,5 ± 0,1. En el caso del SCN es posible observar un comportamiento casi plano para aproximadamente dos órdenes de magnitud.

Con un exponente θ = 0,5 ± 0,1. Este exponente puede estar relacionado con el exponente β al notar que , resultando en β = 1 + θ, si las correlaciones topológicas entre los grados de vértices conectados pueden ser descuidadas. Éste es precisamente el caso de la WAN, donde la relación de escalamiento anterior está bien satisfecha por los valores numéricos proporcionados por las mediciones independientes de los exponentes. En el SCN, en cambio, la fórmula es casi constante durante más de dos décadas, lo que confirma una falta general de correlaciones entre los pesos y los grados de vértice.

Análogamente, un estudio del valor medio s (b) de la fuerza para vértices con intermedios b muestra que el comportamiento funcional puede ser aproximado por una forma de escala  s(b) ∼ b δ  con δSCN ≅ 0.5 y δWAN ≅ 0.8 para el SCN Y la WAN, respectivamente. Como antes, la comparación entre el comportamiento de los datos reales y el caso aleatorizado muestra diferencias más pronunciadas en el caso de la WAN. En ambas redes, la fuerza crece con la intermediación más rápido que en el caso aleatorio, especialmente en la WAN. Este comportamiento es otra clara firma de las correlaciones entre las propiedades ponderadas y la topología de red.

Organización estructural de redes ponderadas

Junto con la jerarquía de vértices impuesta por la distribución de la fuerza, mayores son las redes más centrales y complejas que muestran una arquitectura impuesta por la organización estructural y administrativa de estos sistemas. Por ejemplo, las áreas temáticas y las estructuras nacionales de investigación dan lugar a grupos o comunidades bien definidos en el SCN. En la WAN, por otra parte, las diferentes jerarquías corresponden a grupos aeroportuarios nacionales o regionales y sistemas de transporte intracontinental; Factores políticos o económicos pueden imponer restricciones adicionales a la estructura de la red (13). Para descubrir estas estructuras, algunas cantidades topológicas se estudian habitualmente. El coeficiente de agrupación mide la cohesividad del grupo local y se define para cualquier vértice i como la fracción de vecinos conectados de i (4). El coeficiente de agrupamiento promedio C = N -1Σi c i expresa así el nivel estadístico de cohesividad que mide la densidad global de trillizos de vértices interconectados en la red. Se puede obtener más información inspeccionando el coeficiente de agrupamiento promedio C (k) restringido a clases de vértices con grado k. En redes reales (20, 21), C (k) presenta un comportamiento altamente no trivial con un decaimiento de la ley de potencia en función de k, señalando una jerarquía en la que los vértices de grados bajos pertenecen generalmente a comunidades bien interconectadas (alto coeficiente de agrupación) Mientras que los concentradores conectan muchos vértices que no están conectados directamente (coeficiente de agrupación pequeño) (20, 21). Otra cantidad utilizada para investigar la arquitectura de las redes es el grado medio de vecinos más cercanos, k nn (k), para vértices de grado k (22). Esta última cantidad está relacionada con las correlaciones entre el grado de vértices conectados (22, 23), ya que puede expresarse como k nn(k) = Σk′ k′P(k′|k), donde P(k′|k) es la probabilidad condicional de que un vértice dado con grado k esté conectado a un vértice de grado k'. En ausencia de correlaciones de grados, P(k′|k) no depende de k y tampoco el grado medio de vecinos más cercano; Es decir, k nn(k) = constante (22). En presencia de correlaciones, el comportamiento de k nn(k) identifica dos clases generales de redes. Si k nn(k) es una función creciente de k, los vértices de alto grado tienen una probabilidad mayor de estar conectados con vértices de gran envergadura. Esta propiedad se conoce en física y ciencias sociales como mezclas asortativas (24). Por el contrario, un comportamiento decreciente de k nn(k) define la mezcla desasortativas, en el sentido de que los vértices de alto grado tienen una mayoría de vecinos con grado bajo, mientras que lo contrario ocurre para los vértices de bajo grado.

Las cantidades anteriores proporcionan firmas claras de una organización estructural de redes en las que diferentes clases de grado muestran diferentes propiedades en la estructura de conectividad local. Sin embargo, se definen únicamente en términos topológicos, y la inclusión de pesos y sus correlaciones puede cambiar constantemente nuestra visión de la organización jerárquica y estructural de la red. Esto se puede comprender fácilmente con el ejemplo simple de una red en la que los pesos de todos los bordes que forman triples de vértices interconectados son extremadamente pequeños. Incluso para un gran coeficiente de agrupación, es evidente que estos triples tienen un papel menor en la dinámica de la red y la organización, y que las propiedades de agrupamiento son definitivamente sobrestimado por un simple análisis topológico. De manera similar, los vértices de alto grado podrían estar conectados a una mayoría de vértices de bajo grado mientras que concentran la mayor fracción de su fuerza solamente en los vértices con alto grado. En este caso, la información topológica apunta a propiedades desasistidas, mientras que la red podría considerarse asortativa de manera efectiva, porque los bordes más relevantes en términos de pesos están enlazando vértices de alto grado.

Para resolver las incongruencias anteriores se introducen métricas que combinan la información topológica con la distribución de peso de la red. En primer lugar, consideramos que el coeficiente de agrupamiento ponderado definido como (véase la Fig. 5)

Fig. 5.Ejemplos de configuraciones locales cuyas cantidades topológicas y ponderadas son diferentes. En ambos casos el vértice central (lleno) tiene un enlace muy fuerte con sólo uno de sus vecinos. El agrupamiento ponderado y el grado medio de vecinos más cercanos capturan con mayor precisión el nivel efectivo de cohesividad y afinidad debido a la fuerza de interacción real.

Este coeficiente es una medida de la cohesión local que tiene en cuenta la importancia de la estructura agrupada sobre la base de la cantidad de tráfico o intensidad de interacción realmente encontrada en los trillizos locales. De hecho,  cuenta para cada triplete formado en la vecindad del vértice i el peso de los dos bordes participantes del vértice i. De esta manera, consideramos no sólo el número de trillizos cerrados en el vecindario de un vértice sino también su peso relativo total con respecto a la fuerza del vértice. El factor de normalización si(k i - 1) explica el peso de cada borde multiplicado por el número máximo posible de tripletes en los que puede participar, y asegura que la . Consistentemente, la definición de  recupera el coeficiente de agrupamiento topológico en el caso de que w ij = constante. A continuación, definimos Cw y Cw (k) como el coeficiente de agrupación ponderada promediado sobre todos los vértices de la red y sobre todos los vértices con grado k, respectivamente. Estas cantidades proporcionan información global sobre la correlación entre pesos y topología, especialmente comparándolos con sus análogos topológicos. En el caso de una gran red aleatoria (falta de correlaciones) es fácil ver que Cw = C  y Cw (k) = C(k). En redes ponderadas reales, sin embargo, podemos enfrentar dos casos opuestos. Si Cw > C, estamos en presencia de una red en la que los trillizos interconectados son más probables formados por los bordes con pesos más grandes. Por otro lado, Cw < C señala una red en la que el agrupamiento topológico se genera por los bordes con bajo peso. En este caso, el agrupamiento tiene un efecto menor en la organización de la red porque la mayor parte de las interacciones (tráfico, frecuencia de las relaciones, etc.) se produce en los bordes que no pertenecen a trillizos interconectados. Lo mismo puede suceder para Cw (k), para lo cual también es posible analizar las variaciones con respecto a la clase de grado k.

Junto con el coeficiente de agrupación ponderada, se introduce el grado de vecinos más próximos promedios ponderados, definido como (véase la figura 5)

En este caso, realizamos un promedio local ponderado del grado de vecindad más cercano según el peso normalizado de los bordes de conexión, w ij/s i. Esta definición implica que  si los enlaces con los pesos más grandes están apuntando a los vecinos con mayor grado y  en el caso opuesto. La  mide así la afinidad efectiva para conectar con vecinos de alto o bajo grado según la magnitud de las interacciones reales. Además, el comportamiento de la función  marca las propiedades ponderadas asortativas o desasortativas considerando las interacciones reales entre los elementos del sistema.

Como prueba general, inspeccionamos los resultados obtenidos tanto para el SCN como para la WAN comparando las cantidades topológicas regulares con las obtenidas con la definición ponderada aquí introducida. Las medidas topológicas nos dicen que el SCN tiene un espectro continuamente en descomposición C(k) (véase la figura 6A). Esto implica que los hubs presentan un vecindario agrupado mucho más bajo que los vértices de bajo grado. Este efecto puede interpretarse como la evidencia de que los autores con pocos colaboradores trabajan normalmente dentro de un grupo de investigación bien definido en el que colaboran todos los científicos (agrupación alta). Sin embargo, los autores con un alto grado de colaboración colaboran con diferentes grupos y comunidades, que a su vez no suelen tener colaboraciones, creando así un coeficiente de agrupamiento más bajo. Además, el SCN exhibe una conducta asociativa de acuerdo con la evidencia general de que las redes sociales se denotan generalmente por un fuerte carácter asociativo (24) (véase la figura 6B). El análisis de las cantidades ponderadas confirma este cuadro topológico, proporcionando más información sobre la arquitectura de la red. El coeficiente de agrupamiento ponderado es muy cercano al topológico (Cw /C ≅ 1). Este hecho indica de manera cuantitativa que las colaboraciones de grupo tienden en promedio a ser estables y determinar la intensidad media de las interacciones en la red. Además, la inspección de Cw (k) (ver Fig. 6A) muestra generalmente que para k ≥ 10 el coeficiente de agrupación ponderada es mayor que el topológico. Esta diferencia implica que los autores de alto grado (es decir, con muchos colaboradores) tienden a publicar más artículos con grupos interconectados de coautores. Este hallazgo sugiere que los científicos influyentes forman grupos de investigación estables donde se obtiene la mayor parte de su producción. Finalmente, las propiedades asociativas encuentran una confirmación de corte claro en el análisis ponderado con una  que crece como una potencia de k.


Fig. 6. Cantidades topológicas y ponderadas para el SCN. (A) La agrupación ponderada se separa de la topológica alrededor de k ≥ 10. Este valor marca una diferencia para los autores con mayor número de colaboradores. (B) El comportamiento asortativo se mejora en la definición ponderada del grado medio de vecinos más cercanos.

Una imagen diferente se encuentra en la WAN, donde el análisis ponderado proporciona un escenario más rico y de alguna manera diferente (Fig. 7). Esta red también muestra una C (k) en descomposición, una consecuencia del papel de los grandes aeropuertos que proporcionan conexiones sin escalas a destinos muy lejanos a escala internacional e intercontinental. Estos destinos no suelen estar interconectados entre ellos, dando lugar a un bajo coeficiente de agrupamiento para los hubs. Encontramos, sin embargo, que Cw /C ≅ 1.1, lo que indica una acumulación de tráfico en los grupos interconectados de vértices. El coeficiente de agrupamiento ponderado Cw (k) también tiene un comportamiento diferente en que su variación es mucho más limitada en todo el espectro de k. Esta observación implica que los aeropuertos de alto grado tienen una tendencia progresiva a formar grupos interconectados con enlaces de alto tráfico, equilibrando así la agrupación topológica reducida. Debido a que el alto tráfico está asociado a los hubs, tenemos una red en la que los nodos de alto grado tienden a formar cliques con nodos de igual o mayor grado, el llamado fenómeno del club rico (25). Prueba interesante también emerge de la comparación de k nn(k) y . El k nn(k) topológico muestra un comportamiento asortativo sólo en grados pequeños. Para k> 10, k nn(k) se aproxima a un valor constante, hecho que revela una estructura no correlacionada en la que vértices con grados muy diferentes tienen un vecindario muy similar. Sin embargo, el análisis de la Fórmula ponderada muestra un pronunciado comportamiento asociativo en todo el espectro k, proporcionando una imagen diferente en la que los aeropuertos de alto grado tienen una mayor afinidad con otros grandes aeropuertos en los que se dirige la mayor parte del tráfico.


Fig.7. Cantidades topológicas y ponderadas para la WAN. (A) El coeficiente de agrupación ponderada es mayor que el topológico en todo el espectro de grados. (B) k nn(k) alcanza una meseta para k> 10 que denota la ausencia de correlaciones topológicas marcadas. En contraste, la  exhibe un comportamiento asortativo más definido.

Conclusiones

Hemos demostrado que una visión más completa de las redes complejas se proporciona por el estudio de las interacciones que definen los vínculos de estos sistemas. Los pesos que caracterizan las diversas conexiones muestran características estadísticas complejas con distribuciones muy variables y comportamiento de ley de potencia. En particular, hemos considerado los ejemplos específicos de SCN y WAN donde es posible apreciar la importancia de las correlaciones entre pesos y topología en la caracterización de las propiedades de la red real. De hecho, el análisis de las cantidades ponderadas y el estudio de las correlaciones entre pesos y topología proporcionan una perspectiva complementaria sobre la organización estructural de la red que podría no ser detectada por cantidades basadas únicamente en información topológica. Nuestro estudio ofrece así un enfoque cuantitativo y general para entender la arquitectura compleja de redes ponderadas reales.

Referencias

1. Albert, R. & Barabási, A.-L. (2002) Rev. Mod. Phys. 74 , 47-97. CrossRef | Web of Science | Google Scholar
2. Dorogovtsev, S. N. & Mendes, J. F. F. (2003) Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford Univ. Press, Oxford). Google Scholar
3. Amaral, L. A. N., Scala, A., Barthélemy, M. & Stanley, H. E. (2000) Proc. Natl. Acad. Sci. USA 97 ,11149-11152. Abstract/FREE Full Text
4. Watts, D. J. & Strogatz, S. H. (1998) Nature 393 , 440-442. CrossRef | Medline | Web of Science | Google Scholar
5. Barabási, A.-L & Albert, R. (1999) Science 286 , 509-512. Abstract/FREE | Full Text
6. Cohen, R., Erez, K., ben Avraham, D. & Havlin, S. (2000) Phys. Rev. Lett. 85 , 4626-4628. CrossRef | Medline | Web of Science | Google Scholar 
7. Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J. (2000) Phys. Rev. Lett. 85 , 5468-5471 2000 CrossRef | Medline | Web of Science | Google Scholar 
8. Albert, R., Jeong, H. & Barabási, A.-L. (2000) Nature 406 , 378-382 2000 CrossRef | Medline | Web of Science | Google Scholar
9. Pastor-Satorras, R. & Vespignani, A. (2001) Phys. Rev. Lett. 86 , 3200-3203. CrossRef | Medline | Web of Science | Google Scholar
10. Clark, J. & Holton, D. A. (1998) A First Look at Graph Theory (World Scientific, Singapore). Google Scholar
11. Yook, S. H., Jeong, H., Barabási, A.-L. & Tu, Y. (2001) Phys. Rev. Lett. 86 , 5835-5838.  CrossRef  | Medline | Web of Science | Google Scholar
12. Li, W. & Cai, X. (2003) e-Print Archive, http://xxx.lanl.gov/abs/cond-mat/0309236. Google Scholar
13. Guimerà, R., Mossa, S., Turtschi, A. & Amaral, L. A. N. (2003) e-Print Archive,http://xxx.lanl.gov/abs/cond-mat/0312535.  Google Scholar
14. Newman, M. E. J. (2001) Phys. Rev. E 64 , 016131. CrossRef | Google Scholar
15. Newman, M. E. J. (2001) Phys. Rev. E 64 , 016132. CrossRef | Google Scholar
16. Barabási, A. L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A. & Vicsek, T. (2002) Physica A 311 ,590-614. CrossRef | Web of Science | Google Scholar
17. Freeman, L. C. (1977) Sociometry 40 , 35-41. CrossRef | Web of Science | Google Scholar
18. Goh, K.-I., Kahng, B. & Kim, D. (2001) Phys. Rev. Lett. 87 , 278701. CrossRef | Medline | Google Scholar
19. Brandes, U. (2001) J. Math. Soc. 25 , 163-177. CrossRef | Google Scholar
20. Vázquez, A., Pastor-Satorras, R. & Vespignani, A. (2002) Phys. Rev. E 65 , 066130. CrossRef | Google Scholar
21. Ravasz, E. & Barabási, A.-L. (2003) Phys. Rev. E 67 , 026112. CrossRef | Google Scholar
22. Pastor-Satorras, R., Vázquez, A. & Vespignani, A. (2001) Phys. Rev. Lett. 87 , 258701. CrossRef | Medline | Google Scholar
23. Maslov, S. & Sneppen, K. (2001) Science 296 , 910-913. Google Scholar
24. Newman, M. E. J. (2002) Phys. Rev. Lett. 89 , 208701. CrossRef | Medline | Google Scholar
25. Zhou, S. & Mondragon, R. J. (2003) e-Print Archive, http://xxx.lanl.gov/abs/cs.NI/0303028. Google Scholar

Representando redes complejas con matrices

Retratos de redes complejas

Arxiv
J. P. Bagrow, E. M. Bollt, J. D. Skufca, D. ben-Avraham

Proponemos un método para caracterizar grandes redes complejas mediante la introducción de una nueva estructura de matriz, única para una red dada, que codifica información estructural; Proporciona una visualización útil, incluso para redes muy grandes; Y permite una comparación estadística rigurosa entre redes. Los procesos dinámicos como la percolación se pueden visualizar usando animaciones. Se discuten las aplicaciones a la teoría gráfica, así como generalizaciones a redes ponderadas, pruebas de similitud de red del mundo real y aplicabilidad al problema del isomorfismo de grafos.

703470

Lire plus de publications sur Calaméo

Visualización en Gephi de sitios gubernamentales

Inteligencia en Guerra de (Ciber) Información 

4N6STRIDER


Arriba se ven varios sitios web de departamentos del gobierno de un país, vinculados entre sí y cada departamento está vinculado a un gran cuadro, ¿verdad?
¡Manténganse al tanto!

En el estudio a continuación he rastreado top 10 de sitios web, en un país conocido como sospechoso de estrecha cooperación con ciertos intereses políticos extranjeros.
El propósito de su existencia es difundir la desinformación y manipular la opinión pública.

Es más de 600 miles de enlaces, sin embargo, están conectados a los puntos rojos varios en el centro.
Los puntos rojos no representan a ningún individuo, sólo otra Entidad Internet, no se revela a propósito.

{Imagen 1: El escaneo de un sitio web manipulable revela que en realidad son manejados por una Entidad.}



Por el significado de la misma propaganda que se muestra en este estudio, se puede influir en la democracia misma.
Huelga decir que, gracias a las frases pegadizas, estos sitios web son muy ampliamente citado en las redes sociales, también.

Por favor, piense en el contexto de cualquier información que obtenga, tenga su propia opinión y esté listo para defenderla o cambiarla, si es necesario.
Intentos se hacen para explotar nuestra pereza en nombre de la curiosidad.

A continuación se muestra un ejemplo de la separación semántica de dos partidos políticos diferentes (sitio web). No son conducidos por la misma Entidad, están separados.
Los nodos solitarios son de mala calidad y un poco rotos. Esto podría dar algún espacio a los hacktivistas.

{Imagen 2: Este escaneo muestra, cómo se separa el sitio web de partidos de lados opuestos de espectros políticos, como se esperaba. Es rojo vs blanco.}



Como efecto de estos engaños, falsas noticias y propaganda emitidos por la Entidad, ya se han producido los posibles centros de la llamada radicalización de los ciudadanos.
El siguiente ejemplo muestra la estructura mejor organizada, que tiene sus "células" en todo el país.
Hasta ahora es inofensivo, pero en el futuro estos individuos pueden ser responsables de la manipulación futura.

{Imagen 3: Sitio web del grupo de seguridad nacional autónomo, residente en todos los distritos del país.}



========================================================================

Editar:

El objetivo de este estudio es mostrar ejemplos, cómo el análisis exploratorio de datos y la visualización pueden ayudar también con temas no relacionados con TI.
En este caso particular, esto es regularmente analizado por cualquier Agencia de Inteligencia de País, la cual está obligada a reportar las cuestiones al Primer Ministro / Gobierno.

No pretendo desencadenar la discusión como un conspirador. Por lo tanto, no he revelado de qué país se trata, ni qué sitio web se escanearon. Además, yo llamo a la sombra eminencia sólo "La Entidad" a propósito para evitar la discusión política o más especulaciones.

Y porque me gusta las fotos, va el resto:
(Surgió durante el análisis, tiene el mismo significado que sus fotos relacionadas arriba).

Hacia las estructuras matemáticas de las redes (de grandes datos)

La forma matemática de las cosas por venir

Los conjuntos de datos científicos se están volviendo más dinámicos, requiriendo nuevas técnicas matemáticas a la par con la invención del cálculo.

Quanta Magazine |  Tang Yau Hoong y Jennifer Ouellette



Simon DeDeo, un investigador en matemáticas aplicadas y sistemas complejos en el Instituto Santa Fe, tenía un problema. Colaboraba en un nuevo proyecto que analizaba 300 años de datos de los archivos de Old Bailey de Londres, la corte penal central de Inglaterra y Gales. Por supuesto, había datos limpios en el formato simple de hoja de cálculo de Excel, incluyendo variables tales como acusación, veredicto y sentencia para cada caso. Pero también hubo transcripciones completas de la corte, conteniendo unos 10 millones de palabras registradas durante poco menos de 200.000 ensayos.

-¿Cómo diablos analizas esos datos? -preguntó DeDeo. No era el tamaño del conjunto de datos que era desalentador; Por los grandes estándares de datos, el tamaño era bastante manejable. Fue la complejidad y la falta de estructura formal lo que planteó un problema. Estos "grandes datos" no se parecían a los tipos de conjuntos de datos tradicionales que el antiguo físico habría encontrado antes en su carrera, cuando el paradigma de investigación implicaba formar una hipótesis, decidir precisamente lo que se quería medir, construir un aparato para hacer esa medición tan preciso como sea posible.

Los grandes datos de hoy son ruidosos, desestructurados y dinámicos.

"En física, por lo general tiene un tipo de datos y usted conoce el sistema realmente bien", dijo DeDeo. "Ahora tenemos estos nuevos datos multimodales [extraídos] de sistemas biológicos y sistemas sociales humanos, y los datos se recogen antes incluso de tener una hipótesis". Los datos están ahí en toda su desordenada y multidimensional gloria, esperando ser consultados , Pero ¿cómo se sabe qué preguntas hacer cuando el método científico se ha vuelto en la cabeza?

DeDeo no es el único investigador que está haciendo frente a estos desafíos. A través de cada disciplina, los conjuntos de datos son cada vez más grandes y complejos, ya se trate de registros médicos, secuenciación genómica, redes neuronales en el cerebro, astrofísica, archivos históricos o redes sociales. Alessandro Vespignani, un físico de la Northeastern University que se especializa en aprovechar el poder de las redes sociales para modelar brotes de enfermedades, el comportamiento del mercado de valores, la dinámica social colectiva y los resultados electorales, ha recogido muchos terabytes de datos de redes sociales como Twitter, Crudo y no estructurado. "No definimos las condiciones de los experimentos, así que no sabemos lo que estamos capturando", dijo.


Gunnar Carlsson, un matemático de la Universidad de Stanford, utiliza el análisis de datos topológicos para encontrar estructura en conjuntos de datos complejos y no estructurados.

Los datos grandes de hoy en día son ruidosos, no estructurados y dinámicos en lugar de estáticos. También puede estar dañado o incompleto. "Creemos que los datos están compuestos de vectores, una serie de números y coordenadas", dijo Jesse Johnson, matemático de la Universidad Estatal de Oklahoma. Pero los datos de Twitter o Facebook, o los archivos de prueba del Old Bailey, no parecen nada de eso, lo que significa que los investigadores necesitan nuevas herramientas matemáticas para recoger información útil de los conjuntos de datos. "O se necesita una forma más sofisticada de traducirla en vectores, o se necesita encontrar una forma más generalizada de analizarla", dijo Johnson.

Vespignani utiliza una amplia gama de herramientas matemáticas y técnicas para dar sentido a sus datos, incluyendo el reconocimiento de texto. Él filtra a través de millones de tweets buscando las palabras más relevantes a cualquier sistema que está tratando de modelo. DeDeo adoptó un enfoque similar para el proyecto de archivos Old Bailey. Su solución fue reducir su conjunto de datos iniciales de 100.000 palabras agrupándolas en 1.000 categorías, utilizando palabras clave y sus sinónimos. "Ahora usted ha convertido el juicio en un punto en un espacio de 1000 dimensiones que le dice cuánto el juicio es acerca de la amistad, o la confianza, o la ropa", explicó.

Científicos como DeDeo y Vespignani hacen buen uso de este enfoque poco sistemático para el análisis de datos, pero el matemático de la Universidad de Yale, Ronald Coifman, dice que lo que realmente se necesita es el gran equivalente de datos de una revolución newtoniana, a la par del siglo XVII. Cree que ya está en marcha. No es suficiente, argumenta, simplemente recoger y almacenar cantidades masivas de datos; Deben ser comisariados inteligentemente, y eso requiere un marco global. "Tenemos todos los pedazos del rompecabezas - ahora cómo los montamos realmente así que podemos ver el cuadro grande?" Él dijo. "Puede que tengas un modelo muy simplista a pequeña escala local, pero el cálculo te permite tomar muchos modelos sencillos e integrarlos en un gran cuadro". De manera similar, Coifman cree que la matemática moderna -especialmente la geometría- puede ayudar a identificar los factores globales subyacentes Estructura de grandes conjuntos de datos. Un conjunto de datos podría estar organizado por geografía o clima, por ejemplo, cada uno de los cuales producirá un mapa de formas muy diferentes.

Nodos y enlaces

La ciudad prusiana de Königsberg (ahora Kalingrad), en el Mar Báltico, cuenta con cuatro regiones geográficas distintas divididas por el río Pregel, con siete puentes que conectan esas regiones. En el siglo XVIII, el matemático Leonhard Euler perplejo sobre un enigma popular de esa época: ¿Era posible caminar a través de todos los puentes de Königsberg, cruzar cada uno apenas una vez, y todavía terminar en su punto de partida original? Para resolver el rompecabezas, Euler redujo el problema a uno de los nodos y líneas: Las cuatro regiones terrestres eran los nodos, conectados por los puentes, representados por líneas. Él encontró que para cruzar todos los puentes solamente una vez, cada región de la tierra necesitaría un número par de puentes. Dado que ese no era el caso en Königsberg, tal viaje era imposible.

Los métodos topológicos se parecen mucho a la proyección de una sombra bidimensional de un objeto tridimensional en la pared.
Gunnar Carlsson

Entre las ideas más notables que Euler recogió del rompecabezas fue que las posiciones exactas de los puentes eran irrelevantes para la solución; Todo lo que importaba era el número de puentes y cómo estaban conectados. Los matemáticos ahora reconocen en esto las semillas del campo moderno de la topología.

Tomando una página del libro de ejercicios de Euler, Gunnar Carlsson, un matemático de la Universidad de Stanford, representa complejos y complejos grandes conjuntos de datos como una red de nodos y enlaces, creando un mapa intuitivo de datos basado únicamente en la similitud de los puntos de datos; Esto utiliza la distancia como una entrada que se traduce en una forma o red topológica. Cuanto más similares sean los puntos de datos, más cerca estarán unos de otros en el mapa resultante; Cuanto más diferentes sean, más distantes estarán en el mapa. Esta es la esencia del análisis de datos topológicos (TDA).

TDA es una consecuencia de la máquina de aprendizaje, un conjunto de técnicas que sirve como un caballo de batalla estándar de análisis de datos grandes. Muchos de los métodos de aprendizaje automático son más eficaces cuando se trabaja con matrices de datos, como una hoja de cálculo de Excel, pero ¿qué pasa si su conjunto de datos no se ajusta a ese marco? "El análisis de datos topológicos es una forma de obtener datos estructurados a partir de datos no estructurados para que los algoritmos de aprendizaje automático puedan actuar más directamente en él", dijo Carlsson.

Al igual que con los puentes de Euler, se trata de las conexiones. Las redes sociales trazan las relaciones entre las personas, con grupos de nombres (nodos) y conexiones (aristas) que ilustran cómo todos estamos conectados. Habrá grupos relacionados con la familia, compañeros de la universidad, los conocidos en el lugar de trabajo, y así sucesivamente. Carlsson piensa que es posible extender este enfoque a otros tipos de conjuntos de datos, como las secuencias genómicas. "Uno puede poner las secuencias al lado del otro y contar el número de lugares donde difieren", explicó. "Ese número se convierte en una medida de lo similar o disimilar que son, y se puede codificar como una función de distancia".

La idea es reducir conjuntos de datos grandes y crudos de muchas dimensiones a una representación comprimida en dimensiones inferiores sin sacrificar las propiedades topológicas más relevantes. Idealmente, esto revelará la forma subyacente de los datos. Por ejemplo, una esfera existe técnicamente en todas las dimensiones, pero sólo podemos percibir las tres dimensiones espaciales. Sin embargo, hay gafas matemáticas a través de las cuales uno puede recoger información sobre estas formas de dimensiones superiores, dijo Carlsson. "Una forma es un número infinito de puntos y una cantidad infinita de distancias entre esos puntos. Pero si usted está dispuesto a sacrificar un poco de redondez, puede representar [un círculo] por un hexágono con seis nodos y seis enlaces, y todavía es reconocible como una forma circular.

Esa es la base de la tecnología patentada que Carlsson ofrece a través de su empresa start-up, Ayasdi, que produce una representación comprimida de datos dimensionales altos en bits más pequeños, similar a un mapa del sistema de tubos de Londres. Tal mapa puede no representar exactamente la última característica de definición de la ciudad, pero destaca las regiones primarias y cómo estas regiones están conectadas. En el caso del software de Ayasdi, el mapa resultante no es sólo una visualización llamativa de los datos; También permite a los usuarios interactuar directamente con el conjunto de datos de la misma manera que utilizarían Photoshop o Illustrator. "Significa que no seremos enteramente fieles a los datos, pero si el conjunto de las representaciones inferiores tiene rasgos topológicos, es una buena indicación de que también hay características en los datos originales", dijo Carlsson.

Si su conjunto de datos de alta dimensión tiene 155 variables, ¿cómo empieza a consultarla de una manera que tenga en cuenta todas esas variables? Carlsson compara la tarea con la búsqueda de un martillo en un garaje oscuro. Si la única herramienta que tienes es una linterna, todo lo que puedes hacer es brillar la luz en una pequeña sección del garaje a la vez. Usted puede encontrar el martillo con el tiempo, pero también podría quedarse sin paciencia con el enfoque fragmentado. Sería mucho más eficiente encender una gran luz que ilumina todo el garaje, dándole una perspectiva global. No sólo va a detectar el martillo, pero también se dará cuenta de la caja de clavos sentados al lado de que no se dio cuenta de que era necesario. La tecnología de Ayasdi es similar a iluminar el garaje entero.

Como prueba de principio, Carlsson y colaboradores en Stanford y el Instituto de Estudios Avanzados de Princeton aplicaron este método a un conjunto de datos más tradicionales de un estudio holandés de genómica sobre pacientes con cáncer de mama realizado hace más de una década. Inicialmente se encontraba en la hoja de cálculo estándar de Excel, con 1.500 columnas y 272 filas correspondientes a las muestras genómicas proporcionadas por los sujetos. Una vez que esto se transformó en una red, el "mapa" resultante tomó la forma de una forma Y, codificada por color para indicar qué temas sobrevivieron (azul) y qué sujetos no (rojo). Los pacientes con peores pronósticos se agruparon en la rama izquierda del Y, con la rama derecha compuesta exclusivamente por el 8 al 9 por ciento de los sujetos que sobrevivieron. Una vez que ese grupo había sido identificado, los genetistas podrían analizar los genes más de cerca para determinar cuáles tenían más probabilidades de haber influido en su supervivencia.

El método es lo suficientemente flexible como para ser aplicado a sistemas muy diferentes. Uno de los internos de Carlsson Ayasdi era un nativo de Houston y un fan de los Rockets de Houston. Creó un conjunto de datos de todos los jugadores de la NBA a partir de 2010 y comparó sus medias de la liga en siete categorías estadísticas: puntos, rebotes, asistencias, robos, tiros bloqueados, pérdidas de balón y faltas personales, reducidos a intervalos de un minuto para asegurar que el tiempo de juego No ser un factor.

Si resulta que hay una vaca esférica al acecho debajo de todos sus datos, entonces TDA sería el camino a seguir. Pero si no está allí, ¿qué puedes hacer?
Benjamin Recht

Inicialmente presentó los datos en una hoja de cálculo estándar de Excel, con 400 filas para los jugadores y siete columnas para los puntos de datos, pero el software Ayasdi detectó patrones estadísticos ocultos entre los jugadores, vinculados a sus estilos de juego, y creó un mapa de estas conexiones. El mapa mostró que además de las cinco posiciones principales en el baloncesto - guardia de puntos, guardia de tiro, delantero de potencia, delantero pequeño y centro - había 13 posiciones "ocultas". Él dobló una categoría "protectores de la pintura," los jugadores que realizan bien en el rebote y el bloqueo, pero que acumulan más faltas que puntos. "Los protectores de pintura de puntuación" son similares, pero acumulan menos faltas y más puntos. Este trabajo ganó el premio a la Mejor Evolución del Deporte en la Conferencia MIT Sloan Sports Analytics anual, en parte debido a su potencial utilidad para la identificación de jugadores infravalorados.

Los métodos topológicos se parecen mucho a la proyección de una sombra bidimensional de un objeto tridimensional en la pared: nos permiten visualizar un conjunto de datos grandes y de gran dimensión proyectándolo en una dimensión inferior. El peligro es que, al igual que con las ilusiones creadas por los títeres de la sombra, uno podría estar viendo patrones e imágenes que no están realmente allí.

"Hay una broma matemática terrible que los topólogos no pueden diferenciar entre su parte trasera y una taza de café porque los dos son topológicamente equivalentes", dijo Benjamin Recht, un informático de la Universidad de California, Berkeley, que dice que es tan lejos No está claro cuando TDA funciona y cuando no. La técnica se basa en la suposición de que un conjunto de datos de alta dimensión grande tiene una estructura intrínseca de baja dimensión, y que es posible descubrir esa estructura matemáticamente. Recht cree que algunos conjuntos de datos son intrínsecamente altos en dimensión y no pueden ser reducidos por el análisis topológico. "Si resulta que hay una vaca esférica al acecho debajo de todos sus datos, entonces TDA sería el camino a seguir", dijo. "Pero si no está ahí, ¿qué puede hacer?" Y si su conjunto de datos está dañado o incompleto, los métodos topológicos producirán resultados igualmente dañados.

Bloques de Occam

En febrero de 2004, Emmanuel Candes, un matemático de la Universidad de Stanford, y su entonces postdoc, Justin Romberg, estaban jugando con una imagen mal mutilada en su computadora, el tipo utilizado por los científicos para probar los algoritmos de imágenes. Ellos estaban tratando de encontrar un método para mejorar las imágenes difusas, como las generadas por MRIs cuando no hay tiempo suficiente para completar un escáner. En una corazonada, Candes aplicó un algoritmo diseñado para limpiar imágenes difusas, esperando ver una ligera mejora. Lo que apareció en la pantalla de su computadora en cambio fue una imagen perfectamente renderizada. Candes compara la unlikeliness del resultado a ser dado apenas los tres primeros dígitos de un número de cuenta bancaria de 10 dígitos, y adivinar correctamente los siete dígitos restantes. Pero no fue una casualidad. Lo mismo ocurrió cuando aplicó la misma técnica a otras imágenes incompletas.


La idea detrás del análisis de datos topológicos es reducir los conjuntos de datos de alta dimensión a dimensiones más bajas sin sacrificar las propiedades topológicas más relevantes.

La clave del éxito de la técnica es un concepto conocido como escasez, que suele indicar la complejidad de una imagen, o su ausencia. Es una versión matemática de la navaja de Occam: Aunque puede haber millones de reconstrucciones posibles para una imagen difusa, mal definida, la versión más simple (sparsest) es probablemente el mejor ajuste. De este descubrimiento fortuito, nació la sensación comprimida.

Considere el caso de la transmisión de vídeo en línea. Los datos en bruto de un video son enormes: treinta cuadros de dos megapíxeles por segundo, por lo que los vídeos o las imágenes de las cámaras digitales se almacenan mediante algoritmos de compresión. Por lo general, para realizar la compresión, primero hay que recoger todos los bits y almacenarlos, para que uno pueda descartar los que son menos significativos. Con la detección comprimida, uno puede determinar qué bits son significativos sin primero tener que recoger y almacenarlos todos. Esto, dice Recht, "le permite adquirir imágenes médicas más rápido, hacer mejores sistemas de radar, o incluso tomar fotografías con cámaras de un solo píxel".

"Si examino una población de una enfermedad rara, ¿necesito tantos exámenes de sangre como individuos?", Dijo Candes. "La respuesta es no. Puedo hacer esto con menos pruebas. Mi señal es escasa, ya que sólo se espera que unas pocas personas prueben positivo. "Supongamos que hay una persona infectada en un grupo de 32, y la clínica agrupa las 32 muestras de sangre. Si la prueba es negativa, no hay personas infectadas. Pero si es positivo, ¿cómo puede determinar quién está infectado? Según Candes, usted podría tomar la mitad de las muestras (16) y volver a ejecutar la prueba. Si es positiva, la persona infectada está en este grupo; Si es negativo, el culpable está en la otra mitad. Puede continuar reduciendo las posibilidades dividiendo de nuevo al grupo por la mitad y volviendo a ejecutar la prueba. Este enfoque de "medición holística" le dará la respuesta dentro de cinco pruebas, en comparación con probar cada una de las 32 personas una por una. Esta es la esencia de la detección comprimida.

Usando algoritmos de detección comprimidos, es posible muestrear sólo 100.000 de, digamos, 1 millón de píxeles en una imagen, y todavía ser capaz de reconstruir en resolución completa - siempre que los elementos clave de la escasez y el agrupamiento (o "mediciones holísticas") sean presente. Es útil cada vez que uno encuentra un gran conjunto de datos en el que una fracción significativa de los datos falta o está incompleta. En el caso de los registros médicos, un sensor podría no registrar un punto de datos con precisión, o el personal del hospital podría estar demasiado ocupado para registrar todos los registros en el equipo o podrían registrar la información incorrectamente. Del mismo modo, la detección comprimida podría ser útil para combatir la oclusión en los sistemas de reconocimiento facial. Por ejemplo, usar gafas de sol podría ser problemático si los ojos son una variable clave en el análisis.

Este enfoque puede incluso ser útil para aplicaciones que no son, en sentido estricto, problemas de detección comprimidos, como el premio Netflix. En octubre de 2006, Netflix anunció un concurso que ofrece un gran premio de $ 1 millón a quien pueda mejorar el algoritmo de filtrado para su motor de recomendación cinematográfica en casa, Cinematch. Un equipo internacional de estadísticos, expertos en aprendizaje de máquinas e ingenieros informáticos obtuvo el gran premio en 2009, pero la comunidad académica en general también se benefició, ya que obtuvo acceso a Netflix muy grande, el conjunto de datos de alta calidad. Recht fue uno de los que lo manipularon. Su trabajo confirmó la viabilidad de aplicar el enfoque de detección comprimida al desafío de rellenar las calificaciones perdidas en el conjunto de datos.

Cinematch opera utilizando la retroalimentación de los clientes: Se recomienda a los usuarios que califiquen las películas que ven y basándose en esas calificaciones, el motor debe determinar cuánto le gustará a un usuario dado películas similares. El conjunto de datos es enorme, pero es incompleto: en promedio, los usuarios sólo clasifican alrededor de 200 películas, de casi 18.000 títulos. Dada la enorme popularidad de Netflix, incluso una mejora incremental en el algoritmo predictivo da como resultado un impulso sustancial a la línea de fondo de la compañía. Recht encontró que podía predecir con exactitud qué películas los clientes podían estar interesados ​​en comprar, siempre que él viera suficientes productos por persona. Entre 25 y 100 productos fueron suficientes para completar la matriz.

"Hemos demostrado matemáticamente que usted puede hacer esto con mucha precisión bajo ciertas condiciones mediante técnicas computacionales manejables", dijo Candes, y las lecciones aprendidas de esta prueba de principio están alimentando de nuevo a la comunidad de investigación, abordando problemas en física cuántica, Cristalografía de rayos y visión por ordenador, entre otras aplicaciones. En el futuro, los astrónomos que trabajan con telescopios sensibles a la luz infrarroja sólo necesitarán registrar el 20 por ciento de los píxeles que de otro modo necesitarían para obtener las mismas imágenes de alta resolución, porque la detección comprimida puede llenar los huecos.

Recht y Candes pueden defender enfoques como la detección comprimida, mientras que Carlsson y Coifman se alinean más con el enfoque topológico, pero fundamentalmente, estos dos métodos son complementarios y no competitivos. Hay varias otras herramientas matemáticas prometedoras que se están desarrollando para manejar este valiente nuevo mundo de datos grandes y complicados. Vespignani utiliza todo, desde el análisis de redes, creando redes de relaciones entre personas, objetos, documentos, etc., para descubrir la estructura dentro de los datos, el aprendizaje automático y las buenas estadísticas anticuadas.

Coifman afirma la necesidad de una teoría global subyacente a la par con el cálculo para permitir a los investigadores a ser mejores conservadores de grandes datos. De la misma manera, las diversas técnicas y herramientas que se están desarrollando necesitan integrarse bajo el paraguas de un modelo teórico más amplio. "Al final, la ciencia de los datos es más que la suma de sus partes metodológicas", insiste Vespignani, y lo mismo ocurre con sus herramientas analíticas. "Cuando se combinan muchas cosas se crea algo mayor que es nuevo y diferente."

Resiliencia en las estructuras de redes de servicios multinivel

Pisando suavemente en un mundo conectado

Quanta Magazine

Los modelos matemáticos buscan prevenir el fallo de la red grande siguiente.


Las luces de la ciudad, como se ve en esta imagen compuesta de la NASA, a menudo dependen de un sistema de redes interconectadas que los científicos dicen que puede ser inherentemente 

Gene Stanley nunca baja las escaleras sin sujetarse del pasamanos. Para un joven de 71 años de edad, tiene un miedo mortal de romperse la cadera. En los ancianos, tales interrupciones pueden desencadenar complicaciones fatales, y Stanley, un profesor de física en la Universidad de Boston, cree que sabe por qué.

"Todo depende de todo lo demás", dijo.

Hace tres años, Stanley y sus colegas descubrieron las matemáticas detrás de lo que él llama "la extrema fragilidad de la interdependencia". En un sistema de redes interconectadas como la economía, la infraestructura urbana o el cuerpo humano, su modelo indica que un pequeño apagón en una red puede provocar una cascada a través de todo el sistema, generando una repentina y catastrófica falla generalizada.

El hallazgo, publicado por primera vez en 2010 en la revista Nature, generó más de 200 estudios relacionados, incluyendo análisis del apagón nacional en Italia en 2003, la crisis mundial de los precios de los alimentos de 2007 y 2008 y el "flash crash" de Estados Unidos del 6 de mayo de 2010.

"En las redes aisladas, un poco de daño sólo conducirá a un poco más de daño", dijo Shlomo Havlin, un físico de la Universidad Bar-Ilan en Israel, coautor del artículo de 2010. "Ahora sabemos que debido a la dependencia entre redes, usted puede tener un colapso abrupto."

Mientras que los científicos siguen siendo cautelosos sobre el uso de los resultados de modelos matemáticos simplificados para reingenierizar los sistemas del mundo real, algunas recomendaciones están comenzando a surgir. Basados ​​en refinamientos basados ​​en datos, los nuevos modelos sugieren que las redes interconectadas deben tener copias de seguridad, mecanismos para cortar sus conexiones en tiempos de crisis y regulaciones más estrictas para prevenir fallas generalizadas.

"Hay esperanzas de que algún punto dulce se beneficie de todas las cosas que las redes de redes traen sin ser abrumado por el riesgo", dijo Raissa D'Souza, un complejo teórico de sistemas de la Universidad de California, Davis.


A menudo, las redes de energía, gas, agua, telecomunicaciones y transporte están interrelacionadas. Cuando los nodos de una red dependen de nodos en otro, los fallos de nodos en cualquiera de las redes pueden desencadenar un colapso en todo el sistema.

Para entender la vulnerabilidad de tener nodos en una red depende de nodos en otro, considere la "red inteligente", un sistema de infraestructura en el cual las centrales eléctricas son controladas por una red de telecomunicaciones que a su vez requiere energía de la red de estaciones. De forma aislada, la eliminación de unos pocos nodos de cualquiera de las redes haría poco daño, ya que las señales podrían encaminarse alrededor de la interrupción y llegar a la mayoría de los nodos restantes. Pero en redes acopladas, los nodos derribados en uno eliminan automáticamente los nodos dependientes en el otro, lo que elimina otros nodos dependientes en el primero, y así sucesivamente. Los científicos modelan este proceso en cascada calculando el tamaño del clúster más grande de nodos conectados en cada red, donde la respuesta depende del tamaño del clúster más grande de la otra red. Con los cúmulos interrelacionados de esta manera, una disminución en el tamaño de uno de ellos desencadena una cascada de ida y vuelta de racimos encogibles.

Cuando el daño a un sistema alcanza un "punto crítico", Stanley, Havlin y sus colegas encuentran que el fracaso de un nodo más cede todos los clústeres de red a cero, matando instantáneamente la conectividad en todo el sistema. Este punto crítico variará dependiendo de la arquitectura de un sistema. En uno de los modelos de red acoplada más realistas del equipo, una interrupción del 8 por ciento de los nodos en una red, un nivel plausible de daño en muchos sistemas reales, lleva al sistema a su punto crítico. "La fragilidad que implica esta interdependencia es muy aterradora", dijo Stanley.

Sin embargo, en otro modelo recientemente estudiado por D'Souza y sus colegas, los escasos vínculos entre redes separadas realmente ayudan a suprimir las cascadas a gran escala, demostrando que los modelos de red no son uniformes. Para evaluar el comportamiento de las redes inteligentes, los mercados financieros, los sistemas de transporte y otras redes reales interdependientes, "tenemos que partir del mundo dirigido por los datos y elaborar los modelos matemáticos que capturan los sistemas reales en lugar de usar modelos porque Son bastante y analíticamente manejables ", dijo D'Souza.

En una serie de artículos en la edición de marzo de Nature Physics, economistas y físicos utilizaron la ciencia de las redes interconectadas para identificar el riesgo dentro del sistema financiero. En un estudio, un grupo interdisciplinario de investigadores, entre ellos el economista Joseph Stiglitz, ganador del Premio Nobel, encontró inestabilidades inherentes dentro del complejo mercado de derivados, de múltiples trillones de dólares, y sugirió regulaciones que podrían ayudar a estabilizarlo.

Irena Vodenska, profesora de finanzas de la Universidad de Boston, que colabora con Stanley, diseñó un modelo de red acoplada en torno a los datos de la crisis financiera de 2008. El análisis de ella y sus colegas, publicado en febrero en Scientific Reports, mostró que modelar el sistema financiero como una red de dos redes -bancos y activos bancarios, donde cada banco está vinculado a los activos que tenía en 2007- predijo correctamente qué bancos Fallan el 78 por ciento del tiempo.

"Consideramos este modelo como potencialmente útil para las pruebas de estrés de riesgo sistémico para los sistemas financieros", dijo Vodenska, cuya investigación está financiada por el programa de predicción de la crisis financiera de la Unión Europea. A medida que la globalización enreda aún más las redes financieras, dijo, las agencias reguladoras deben monitorear las "fuentes de contagio" -concentraciones en ciertos activos, por ejemplo- antes de que puedan causar epidemias de fracaso. Para identificar estas fuentes, "es imprescindible pensar en el sentido de redes de redes", dijo.


Leonardo Dueñas-Osorio, ingeniero civil de Rice, visitó una subestación de alto voltaje dañada en Chile luego de un gran terremoto en 2010 para obtener información sobre la respuesta de la red eléctrica a la crisis.

Los científicos están aplicando ideas similares a la evaluación de la infraestructura. Leonardo Dueñas-Osorio, ingeniero civil de la Universidad de Rice, está analizando cómo los sistemas de salvavidas respondieron a los recientes desastres naturales. Cuando un terremoto de 8,8 grados de magnitud golpeó Chile en 2010, por ejemplo, la mayor parte de la red eléctrica se restauró después de sólo dos días, ayudando a los trabajadores de emergencia. La rápida recuperación, según sugiere la investigación de Dueñas-Osorio, se produjo porque las centrales eléctricas de Chile se desacoplaron inmediatamente del sistema de telecomunicaciones centralizado que usualmente controlaba el flujo de electricidad a través de la red, pero que se redujo en algunas áreas. Las centrales eléctricas fueron operadas localmente hasta que el daño en otras partes del sistema disminuyó.

"Después de un evento anormal, la mayoría de los efectos perjudiciales ocurren en los primeros ciclos de interacción mutua", dijo Dueñas-Osorio, quien también está estudiando la respuesta de la ciudad de Nueva York al huracán Sandy en octubre pasado. "Así que cuando algo va mal, necesitamos tener la capacidad de desacoplar las redes para evitar los efectos de ida y vuelta entre ellos".

D'Souza y Dueñas-Osorio están colaborando para construir modelos precisos de sistemas de infraestructura en Houston, Memphis y otras ciudades americanas con el fin de identificar las debilidades del sistema. "Los modelos son útiles para ayudarnos a explorar configuraciones alternativas que podrían ser más efectivas", explicó Dueñas-Osorio. Y como la interdependencia entre las redes aumenta naturalmente en muchos lugares, "podemos modelar esa integración superior y ver qué pasa".

Los científicos también están buscando en sus modelos respuestas sobre cómo arreglar los sistemas cuando fallan. "Estamos en el proceso de estudiar cuál es la manera óptima de recuperar una red", dijo Havlin. "Cuando las redes fallan, ¿qué nodo se arreglan primero?"

La esperanza es que las redes de redes puedan ser inesperadamente resistentes por la misma razón que son vulnerables. Como dijo Dueñas-Osorio: "Al hacer mejoras estratégicas, ¿podemos tener lo que equivale a cascadas positivas, donde una pequeña mejora propaga beneficios mucho mayores?"

Estas preguntas abiertas tienen la atención de los gobiernos de todo el mundo. En Estados Unidos, la Agencia para la Reducción de las Amenazas a la Defensa, una organización encargada de salvaguardar la infraestructura nacional contra las armas de destrucción masiva, considera el estudio de las redes interdependientes su "máxima prioridad de misión" en la categoría de investigación básica. Algunas aplicaciones de defensa ya han surgido, como un nuevo diseño para sistemas de redes eléctricas en bases militares. Pero gran parte de la investigación pretende clasificar las sutilezas matemáticas de la interacción de la red.

"Todavía no estamos en el nivel" vamos a ingeniar la Internet de manera diferente ", dijo Robin Burk, un científico de la información y ex director del programa DTRA que dirigió el enfoque de la agencia en la investigación de redes interdependientes. "Una buena parte de ella sigue siendo ciencia básica - ciencia desesperadamente necesaria."