Introducción a las redes complejas (análisis de redes)
Las redes, llamadas gráficas en matemáticas, se estudiaron por primera vez con el problema de los Siete Puentes de Königsberg de Euler en 1736. Sin embargo, la investigación sobre gráficas se desarrolló lentamente después de eso. No fue hasta 1936 que se publicó el primer libro Works. sobre la investigación de la teoría de grafos.
En 1960, los matemáticos Erdos y Renyi establecieron la teoría de grafos aleatorios, que proporcionó un nuevo método para construir redes. En este método, si existe una conexión de borde entre dos nodos ya no es una cosa determinada, sino que se determina en función de una probabilidad. La red generada de esta manera se denomina red aleatoria. La idea de gráficos aleatorios ha dominado la investigación sobre redes complejas durante cuarenta años. Sin embargo, hasta los últimos años, los científicos han obtenido muchos resultados después de calcular y estudiar una gran cantidad de datos reales de redes reales. No es completamente aleatoria, no es una red regular ni una red aleatoria, sino una red con características estadísticas diferentes a las dos primeras. Estas redes se denominan redes complejas y el estudio de redes complejas marca la llegada de la tercera etapa de la investigación de redes.
En 1998, Watts y su mentor Strogatz publicaron un artículo "Dinámica colectiva de redes de mundos pequeños" en Nature, describiendo las características del gran coeficiente de cohesión y la corta longitud de ruta promedio de las redes en el mundo pequeño. . Posteriormente, en 1999, Barabasi y su estudiante de doctorado Albert propusieron un modelo de red sin escala (la distribución de grados es una distribución de ley de potencia) en el artículo "Emergence of Scaling in Random Networks" en Science, que describe el omnipresente fenómeno del "hombre rico". En las redes reales, el fenómeno de "hacerse más rico" ha abierto desde entonces una nueva era de investigación de redes complejas.
Con la profundización de la investigación, se han descubierto cada vez más propiedades de las redes complejas. Uno de los estudios más importantes es el artículo "Estructura comunitaria en" publicado por Girvan y Newman en PNAS en 2002. "Social. and Biological Networks", señaló que las características de agrupamiento son omnipresentes en redes complejas, y cada clase se llama comunidad, y propuso un algoritmo para descubrir estas comunidades. Desde entonces, se han realizado muchas investigaciones sobre el problema del descubrimiento de comunidades en redes complejas y se han producido una gran cantidad de algoritmos.
Muchos sistemas complejos se pueden modelar como una red compleja para su análisis, como redes eléctricas comunes, redes de aviación, redes de transporte, redes informáticas, redes sociales, etc. La red compleja no es sólo una representación de datos, también es un método de investigación científica.
Definición de red compleja
Qian Xuesen dio una definición estricta de red compleja:
La red compleja tiene las características de una longitud de ruta de red promedio pequeña, agrupamiento Los coeficientes son grandes y los grados de los nodos obedecen a la distribución de la ley de potencia.
Por implicación, una red compleja se refiere a una red que exhibe un alto grado de complejidad. Sus características se reflejan principalmente en los siguientes aspectos: p>
La teoría del mundo pequeño también se llama teoría del espacio de seis dimensiones o teoría de los seis grados de separación. La propiedad de Small World afirma que no habrá más de seis personas entre cualquier miembro de la red social y cualquier extraño.
Al considerar las características de la red, generalmente se utilizan dos características para medir la red:
Para redes regulares, la longitud de la ruta característica entre dos puntos (individuos) cualesquiera es larga (a través de cuántos los individuos están vinculados entre sí), pero el coeficiente de agregación es alto (la probabilidad de que seas amigo de un amigo de un amigo es alta). Para redes aleatorias, la longitud del camino característico entre dos puntos cualesquiera es corta, pero el coeficiente de agregación es bajo.
En la red del mundo pequeño, la longitud del camino característico entre puntos es pequeña, cercana a una red aleatoria, mientras que el coeficiente de agregación sigue siendo bastante alto, cercano a una red regular.
Las características de mundo pequeño de las redes complejas están estrechamente relacionadas con la difusión de información en la red. Las redes sociales, ecológicas y de otro tipo reales son redes de mundo pequeño. En tales sistemas, la velocidad de transmisión de información es rápida y un pequeño cambio en algunas conexiones puede cambiar drásticamente el rendimiento de la red, como ajustar la red existente. , en las redes de telefonía móvil, el rendimiento se puede mejorar significativamente cambiando sólo unas pocas líneas.
La mayoría de las redes en el mundo real no son redes aleatorias. Una pequeña cantidad de nodos a menudo tienen una gran cantidad de conexiones, mientras que la mayoría de los nodos tienen muy pocas. La distribución de grados de los nodos se ajusta a una distribución de ley de potencia. y esto se llama Es la propiedad sin escala de la red. Una red compleja cuya distribución de grados se ajusta a una distribución de ley de potencia se denomina red sin escala.
Por ejemplo, la distribución de números de usuarios en Zhihu:
La característica sin escala refleja la grave heterogeneidad de las redes complejas y el estado de conexión entre sus nodos (Grado). Distribución desigual grave: unos pocos nodos en la red llamados nodos Hub tienen muchísimas conexiones, mientras que la mayoría de los nodos tienen solo una cantidad muy pequeña de conexiones. Un pequeño número de puntos centrales desempeñan un papel destacado en el funcionamiento de redes sin escala. En términos generales, la naturaleza libre de escala de las redes libres de escala es una propiedad intrínseca que describe la grave distribución desigual de una gran cantidad de sistemas complejos en su conjunto.
De hecho, las características sin escala de las redes complejas están estrechamente relacionadas con el análisis de robustez de la red. La existencia de características de distribución de ley de potencia en redes sin escala aumenta en gran medida la posibilidad de que existan un gran número de nodos. Por lo tanto, las redes sin escala muestran simultáneamente robustez contra fallas aleatorias y vulnerabilidad contra ataques deliberados. Esta robustez y vulnerabilidad tiene un gran impacto en la tolerancia a fallas de la red y la resistencia a ataques.
Las investigaciones muestran que las redes sin escala tienen una fuerte tolerancia a fallas, pero para ataques selectivos basados en valores de grado de nodo, su resistencia a los ataques es bastante pobre y la existencia de un gran número de nodos debilita en gran medida la capacidad de resistir. ataques Debido a la solidez de la red, un atacante malicioso solo necesita elegir atacar una pequeña cantidad de nodos en la red para paralizarla rápidamente.
Las personas de la misma especie se juntan y las cosas se dividen en grupos. Los nodos de redes complejas a menudo también presentan características de clúster. Por ejemplo, en las redes sociales siempre hay círculos de conocidos o amigos, en los que cada miembro conoce a todos los demás. El significado del grado de agrupación es el grado de agrupación de la red; esta es una tendencia de cohesión de la red. El concepto de grupos conectados refleja la distribución e interconexión de pequeñas redes reunidas en una gran red. Por ejemplo, puede reflejar la relación mutua entre este círculo de amigos y otro círculo de amigos.
La siguiente figura es una descripción del fenómeno de agregación de redes:
Las características del mundo pequeño, la distribución de la ley de potencia sin escala o el alto grado de agregación exhibido por las redes reales incitan a las personas a comenzar A partir de la teoría se construyen varios modelos de redes para explicar estas características estadísticas y explorar los mecanismos evolutivos que forman estas redes. Esta sección presenta los principios y métodos de construcción de varios modelos de red clásicos, incluido el modelo de red aleatoria ER, el modelo de red sin escala BA y el modelo de mundo pequeño.
El modelo de red aleatoria ErdOs-Renyi (modelo de red aleatoria ER para abreviar) es un modelo de red propuesto por los matemáticos húngaros Erdos y Renyi. En 1959, para describir las redes en las comunicaciones y las ciencias de la vida, Erdos y Renyi propusieron que tales sistemas podrían simularse de manera efectiva organizando aleatoriamente conexiones entre los nodos de la red. La simplicidad y concisión de este método y los teoremas relacionados condujeron a un renacimiento en la investigación de la teoría de grafos, y surgió un nuevo campo de investigación sobre redes aleatorias en la comunidad matemática. Los modelos de redes aleatorias ER se han utilizado ampliamente en informática, física estadística, ciencias biológicas, ingeniería de comunicaciones y otros campos.
El modelo de red aleatoria ER es un modelo de red que ofrece igualdad de oportunidades.
En este modelo de red, dado un cierto número de individuos (nodos), la probabilidad de una relación mutua (conexión) entre él y cualquier otro individuo (nodo) es la misma, que se registra como un hogar. Porque la probabilidad de que un nodo conecte k otros nodos disminuirá exponencialmente a medida que aumente el valor de k. De esta manera, si la definición es el número de otros individuos conectados a cada individuo, podemos saber que la probabilidad de conexión p (k) obedece a la distribución de Poisson en forma de campana. A veces, las redes aleatorias también se denominan redes exponenciales.
Una predicción importante de la teoría de redes aleatorias es que, aunque las conexiones se colocan aleatoriamente, la red resultante es altamente democrática, es decir, la mayoría de los nodos tendrán aproximadamente el mismo número de conexiones. De hecho, es muy raro que una red aleatoria tenga nodos con un número de conexiones mucho mayor o menor que el promedio.
Durante más de 40 años, los científicos se han acostumbrado a tratar todas las redes complejas como redes aleatorias. Cuando trabajaban en un proyecto de 1998 para mapear la World Wide Web (con páginas web como nodos e hipervínculos como bordes), los académicos esperaban encontrar una red aleatoria: las personas decidirían qué sitios vincular a archivos web en función de sus intereses individuales. diverso y la cantidad de páginas web para elegir es extremadamente grande, por lo que el patrón de enlace final parecerá bastante aleatorio.
Sin embargo, este no es el caso. Porque en la World Wide Web no todos los nodos son iguales. Al elegir dónde vincular a una página web, las personas pueden elegir entre miles de millones de sitios web. Sin embargo, la mayoría de nosotros sólo estamos familiarizados con una pequeña porción de toda la World Wide Web, y esta pequeña porción tiende a incluir sitios con más enlaces porque es más probable que dichos sitios sean conocidos. El simple hecho de vincular a estos sitios crea o refuerza una preferencia por ellos. Este proceso de “Vínculo Preferencial” también se da en otras redes. En Internet, los enrutadores con más conexiones suelen tener mayor ancho de banda, por lo que es más probable que nuevos usuarios se conecten a estos enrutadores. Dentro de la industria biotecnológica estadounidense, es más probable que ciertas empresas conocidas atraigan aliados, lo que aumenta aún más su atractivo para futuras colaboraciones. De manera similar, en la red de citas de artículos (los artículos son nodos y las relaciones de citas son bordes), los documentos científicos que han sido citados más veces atraerán a más investigadores para leerlos y citarlos. En respuesta a las nuevas características de las "conexiones preferidas" en estas redes, los académicos han propuesto el modelo de red sin escala BA.
El descubrimiento de redes sin escala ha llevado la comprensión humana de las redes complejas a un mundo nuevo. La característica más importante de las redes sin escala es que la distribución de grados de los nodos obedece a una ley potencial. El modelo BA es el primer modelo abstracto de Scale-free Network. Dado que se tiene en cuenta el crecimiento y la conectividad preferencial del sistema, el modelo BA nos ha traído mucha inspiración y se puede aplicar a una variedad de redes reales. Sin embargo, los dos supuestos básicos del modelo BA son demasiado simples para explicar muchos fenómenos de la vida real y todavía hay una gran distancia con respecto a las redes reales.
Algunos académicos han intentado expandir el modelo BA, es decir, agregar ciertos supuestos basados en redes reales para explorar más a fondo las leyes de los sistemas de redes complejos. Se pueden considerar tres factores en la expansión del modelo BA: el costo de la selección preferencial, la reconexión del borde y el estado inicial de la red. El modelo BA ampliado puede simular mejor los fenómenos de la red en el mundo real.
En 1999, Maru Barabasi y su hermano Albert descubrieron redes sin escala durante sus investigaciones en Internet, lo que dio a la humanidad una nueva comprensión de los sistemas de redes complejos. En el pasado, la gente estaba acostumbrada a tratar todas las redes complejas como redes aleatorias, pero Barabasi y Albert descubrieron que Internet en realidad está organizada por una pequeña cantidad de páginas altamente conectadas, y más del 80% de las páginas tienen menos de 4 enlaces. Un número muy pequeño de nodos, que representan menos de una diezmilésima parte del número total de nodos, tienen más de 1.000 enlaces. La distribución de enlaces de este tipo de páginas web sigue la llamada "ley de potencia": la probabilidad de que cualquier nodo tenga un enlace es proporcional a 1/k.
No tiene un pico concentrado como una curva de campana, sino una curva que decrece continuamente. Si utilizamos un sistema de coordenadas logarítmico para describir la ley de potencia, obtenemos una línea recta.
La red sin escala se refiere a una red en la que la distribución de grados de los nodos se ajusta a una distribución de ley de potencia. Se denomina red sin escala porque carece de una escala característica para describir el problema. En los años siguientes, los investigadores descubrieron redes sin escala en muchos campos diferentes. Desde los ecosistemas hasta las relaciones interpersonales, desde las cadenas alimentarias hasta los sistemas metabólicos, se pueden ver redes sin escala por todas partes.
¿Por qué el modelo estocástico es inconsistente con la realidad? Después de un análisis en profundidad del modelo ER, Barabasi y Albert descubrieron que el problema es que la red discutida por el modelo ER es una red de una escala determinada y no seguirá expandiéndose. Precisamente porque la red real a menudo tiene las características de crecimiento continuo, los nodos que ingresaron temprano (nodos antiguos) tienen una mayor probabilidad de obtener una conexión. Cuando la red se expande a una cierta escala, estos nodos antiguos pueden convertirse fácilmente en nodos centrales con una gran cantidad de conexiones. Este es el "crecimiento" de Internet.
En segundo lugar, cuando cada nodo en el modelo ER está conectado a otros nodos, la probabilidad de establecer una conexión es la misma. En otras palabras, todos los nodos de la red son iguales. Esta situación también es inconsistente con la realidad. Por ejemplo, cuando un sitio web recién creado elige vincularse a otros sitios web, naturalmente elegirá uno de los sitios web conocidos para vincularlo. Es más probable que los enlaces de hipertexto en la nueva página de inicio personal apunten a sitios famosos como Sina y. Yahoo. Como resultado, esos sitios web conocidos obtendrán más enlaces, una característica llamada "enlaces preferenciales". Este fenómeno también se conoce como "efecto Matthew" o "los ricos se hacen más ricos".
Los dos mecanismos de "crecimiento" y "conexión preferencial" explican la existencia de nodos de distribución en la red.
La clave del modelo sin escala de BA es que atribuye las características sin escala de redes complejas reales a dos mecanismos muy simples: crecimiento y conexión preferencial. Por supuesto, esto inevitablemente hace que el modelo de red sin escala de BA tenga algunas limitaciones obvias en comparación con la red real. Por ejemplo, la influencia de algunas características locales de las redes reales en los resultados de la evolución de la red, la influencia del mundo exterior en la eliminación de los nodos de la red y sus bordes de conexión, etc.
Generalmente, existen intercambios de nodos entre redes reales naturales o artificiales y el mundo exterior, y las conexiones entre los nodos cambian constantemente. La red en sí tiene ciertas capacidades de autoorganización y responderá en consecuencia a los cambios. en sí mismo o en la reacción del mundo exterior. Por lo tanto, con base en el modelo BA, el proceso dinámico del modelo se puede generalizar, incluida la eliminación aleatoria de nodos o conexiones existentes en la red y su correspondiente mecanismo de compensación de conexión.
Para cada paso de tiempo, considere las siguientes tres suposiciones:
Un hallazgo importante en la investigación de redes complejas es que la longitud promedio de la ruta de la mayoría de las redes reales a gran escala es más larga de lo imaginado. Más pequeño, se llama "fenómeno del mundo pequeño" o "Seis grados de separación".
El llamado fenómeno del mundo pequeño proviene del fenómeno básico de las redes sociales, es decir, cada persona sólo necesita unos pocos intermediarios (una media de 6) para establecer conexiones con personas de todo el mundo. En esta teoría, cada persona puede considerarse como un nodo en la red y hay una gran cantidad de caminos que los conectan. Los nodos conectados representan personas que se conocen entre sí.
En 1998, Watts y Strogatz introdujeron un modelo de red de mundo pequeño de un solo parámetro entre redes regulares y redes completamente aleatorias, llamado modelo de mundo pequeño WS. Este modelo refleja mejor la red social. Hay dos fenómenos. de longitud de camino promedio pequeña y coeficiente de agrupamiento grande.
El método de construcción del modelo de mundo pequeño de WS es el siguiente:
En el modelo de mundo pequeño de WS, p=0 corresponde a una red regular y p=l corresponde a una red completamente aleatoria Al ajustar el valor del sonido se puede controlar la transición de una red normal a un gráfico completamente aleatorio.
Por lo tanto, la red WS Small World es un tipo de red entre una red regular y una red aleatoria.
El proceso de aleatorización en el algoritmo de construcción del modelo de mundo pequeño de WS puede destruir la conectividad de la red. Por lo tanto, Newman y Watts propusieron más tarde el modelo de mundo pequeño del noroeste. El método de construcción del modelo de mundo pequeño NW es el siguiente:
El modelo NW simplemente cambia la "reconexión aleatoria" en la construcción del modelo de mundo pequeño WS a "adición de bordes aleatoria".
El modelo NW se diferencia del modelo WS en que no corta los bordes originales en la red regular, sino que reconecta un par de nodos con probabilidad p. La red construida de esta manera tiene una gran cantidad de grupos y una distancia promedio pequeña. La ventaja del modelo NW es que simplifica el análisis teórico, porque el modelo WS puede tener nodos aislados, pero el modelo NW no. Cuando el hogar es lo suficientemente pequeño y N es lo suficientemente grande, el modelo de mundo pequeño del noroeste es esencialmente equivalente al modelo de mundo pequeño del oeste.
El modelo de red de mundo pequeño refleja algunas características de las redes reales, como las redes de amigos. La mayoría de los amigos de las personas viven en el mismo lugar que ellos y su ubicación geográfica no está muy lejos, o solo sus colegas y. compañeros que trabajan o estudian en la misma unidad. Por otro lado, también hay personas que viven lejos, o incluso amigos en países extranjeros. Esta situación es como la conexión remota creada al volver a cablear en el modelo de mundo pequeño WS o al unirse a la conexión en el modelo de mundo pequeño NW.
Una de las principales características del modelo de red de mundo pequeño es que la distancia media entre nodos disminuye exponencialmente con el número de conexiones remotas. Para redes regulares, la distancia promedio L se puede estimar como L es proporcional a N, mientras que para modelos de redes de mundo pequeño, L es proporcional a ln(N)/1n(K). Por ejemplo, en una ciudad con una población de 10 millones, la distancia de contacto promedio entre personas es de aproximadamente 6, lo que acorta en gran medida la distancia entre los grupos de viviendas. El modelo consta de un anillo regular, generalmente un anillo unidimensional con condiciones de contorno casi periódicas (es decir, cada nodo del anillo está casi conectado a un número fijo de nodos vecinos) y un pequeño número de "atajos" seleccionados al azar. " (reconectando los bordes existentes). La red del mundo pequeño tiene las características de "alta agregación de red" y "ruta promedio baja" al mismo tiempo.
Se puede ver en el modelo de red del mundo pequeño que siempre que se cambien algunas conexiones, el rendimiento de la red puede cambiar drásticamente. Estas propiedades también se pueden aplicar a otras redes, especialmente en el ajuste de redes existentes. Por ejemplo, en una red de telefonía celular, el rendimiento se puede mejorar significativamente modificando las conexiones de sólo unas pocas líneas (de bajo costo y bajo esfuerzo). También se puede aplicar a los enrutadores troncales de Internet para cambiar el tráfico y aumentar las velocidades de transmisión. La misma idea también se puede aplicar a la entrega rápida de correo electrónico, al posicionamiento de sitios web específicos, etc.
Si quieres aprender redes complejas, los mejores vídeos tutoriales actualmente son:
Computación Social y Análisis de Redes Sociales Análisis de Redes
1) Algoritmo de clustering en complejos Resumen de redes
2) Resumen del análisis de redes de análisis de redes complejas
3) Red compleja y red social