Ciencia de redes

Campo académico

La ciencia de redes es un campo académico que estudia redes complejas como redes de telecomunicaciones , redes de computadoras , redes biológicas , redes cognitivas y semánticas y redes sociales , considerando elementos o actores distintos representados por nodos (o vértices ) y las conexiones entre los elementos o actores como enlaces (o aristas ). El campo se basa en teorías y métodos que incluyen la teoría de grafos de las matemáticas, la mecánica estadística de la física, la minería de datos y la visualización de la información de la informática, el modelado inferencial de la estadística y la estructura social de la sociología. El Consejo Nacional de Investigación de los Estados Unidos define la ciencia de redes como "el estudio de las representaciones en red de fenómenos físicos, biológicos y sociales que conducen a modelos predictivos de estos fenómenos". ^[1]

Antecedentes e historia

El estudio de redes ha surgido en diversas disciplinas como un medio para analizar datos relacionales complejos. El primer artículo conocido en este campo es el famoso Los siete puentes de Königsberg escrito por Leonhard Euler en 1736. La descripción matemática de Euler de los vértices y las aristas fue la base de la teoría de grafos , una rama de las matemáticas que estudia las propiedades de las relaciones por pares en una estructura de red. El campo de la teoría de grafos continuó desarrollándose y encontró aplicaciones en la química (Sylvester, 1878).

Dénes Kőnig , matemático y profesor húngaro, escribió el primer libro sobre teoría de grafos, titulado "Teoría de grafos finitos e infinitos", en 1936. ^[2]

Sociograma de Moreno de una clase de 1er grado.

En la década de 1930, Jacob Moreno , un psicólogo de la tradición Gestalt , llegó a los Estados Unidos. Desarrolló el sociograma y lo presentó al público en abril de 1933 en una convención de académicos médicos. Moreno afirmó que "antes de la llegada de la sociometría nadie sabía cómo era 'precisamente' la estructura interpersonal de un grupo". ^[3] El sociograma era una representación de la estructura social de un grupo de estudiantes de primaria. Los chicos eran amigos de chicos y las chicas eran amigas de chicas con la excepción de un chico que dijo que le gustaba una chica soltera. El sentimiento no era recíproco. Esta representación en red de la estructura social se consideró tan intrigante que se publicó en The New York Times . ^[4] El sociograma ha encontrado muchas aplicaciones y se ha convertido en el campo del análisis de redes sociales .

La teoría probabilística en la ciencia de redes se desarrolló como una derivación de la teoría de grafos con los ocho artículos famosos de Paul Erdős y Alfréd Rényi sobre grafos aleatorios . Para las redes sociales, el modelo de grafo aleatorio exponencial o p* es un marco de notación utilizado para representar el espacio de probabilidad de que ocurra un empate en una red social . Un enfoque alternativo a las estructuras de probabilidad de red es la matriz de probabilidad de red , que modela la probabilidad de que ocurran aristas en una red, en función de la presencia o ausencia histórica de la arista en una muestra de redes.

En 1998, David Krackhardt y Kathleen Carley introdujeron la idea de una metared con el modelo PCANS. ^[5] Sugieren que "todas las organizaciones están estructuradas a lo largo de estos tres dominios: individuos, tareas y recursos". Su artículo introdujo el concepto de que las redes se producen en múltiples dominios y que están interrelacionadas. Este campo se ha convertido en otra subdisciplina de la ciencia de redes llamada análisis dinámico de redes .

Más recientemente, otros esfuerzos de la ciencia de redes se han centrado en describir matemáticamente diferentes topologías de red. Duncan Watts y Steven Strogatz conciliaron datos empíricos sobre redes con representación matemática, describiendo la red de mundo pequeño . ^[6] Albert-László Barabási y Reka Albert descubrieron redes libres de escala , ^[7] una propiedad que captura el hecho de que en la red real los centros coexisten con muchos vértices de grado pequeño, y ofrecieron un modelo dinámico para explicar el origen de este estado libre de escala.

Iniciativas del Departamento de Defensa

El ejército de los Estados Unidos se interesó por primera vez en la guerra centrada en redes como un concepto operativo basado en la ciencia de redes en 1996. John A. Parmentola, Director de Investigación y Gestión de Laboratorios del Ejército de los Estados Unidos, propuso a la Junta de Ciencia y Tecnología (BAST) del Ejército el 1 de diciembre de 2003 que la Ciencia de Redes se convirtiera en una nueva área de investigación del Ejército. La BAST, la División de Ingeniería y Ciencias Físicas del Consejo Nacional de Investigación (NRC) de las Academias Nacionales, actúa como autoridad de convocatoria para la discusión de cuestiones científicas y tecnológicas de importancia para el Ejército y supervisa estudios independientes relacionados con el Ejército realizados por las Academias Nacionales. La BAST realizó un estudio para averiguar si la identificación y financiación de un nuevo campo de investigación en la investigación básica, la Ciencia de Redes, podría ayudar a cerrar la brecha entre lo que se necesita para realizar Operaciones Centradas en Redes y el estado primitivo actual de conocimiento fundamental de las redes.

Como resultado, el BAST publicó en 2005 el estudio del NRC titulado Network Science (Ciencia de redes) (mencionado anteriormente) que definió un nuevo campo de investigación básica en Ciencia de redes para el Ejército. Con base en los hallazgos y recomendaciones de ese estudio y el informe del NRC de 2007 posterior titulado Strategy for an Army Center for Network Science, Technology, and Experimentation (Estrategia para un centro del Ejército para la ciencia, tecnología y experimentación de redes), los recursos de investigación básica del Ejército se reorientaron para iniciar un nuevo programa de investigación básica en Ciencia de redes. Para construir una nueva base teórica para redes complejas, algunas de las principales iniciativas de investigación en Ciencia de redes que se están llevando a cabo actualmente en los laboratorios del Ejército abordan:

• Modelos matemáticos del comportamiento de la red para predecir el rendimiento con el tamaño de la red, la complejidad y el entorno.
• Se requiere un rendimiento humano optimizado para la guerra en red
• Creación de redes dentro de los ecosistemas y a nivel molecular en las células.

Tal como lo inició Frederick I. Moxley en 2004 con el apoyo que solicitó de David S. Alberts, el Departamento de Defensa ayudó a establecer el primer Centro de Ciencias de Redes en conjunto con el Ejército de los EE. UU. en la Academia Militar de los Estados Unidos (USMA). Bajo la tutela del Dr. Moxley y el cuerpo docente de la USMA, se enseñaron los primeros cursos interdisciplinarios de pregrado en Ciencias de Redes a los cadetes de West Point. ^{[8] [9] [10]} Para inculcar mejor los principios de la ciencia de redes entre su grupo de futuros líderes, la USMA también ha instituido una especialización de pregrado de cinco cursos en Ciencias de Redes. ^[11]

En 2006, el Ejército de los EE. UU. y el Reino Unido (RU) formaron la Network and Information Science International Technology Alliance , una asociación de colaboración entre el Laboratorio de Investigación del Ejército, el Ministerio de Defensa del Reino Unido y un consorcio de industrias y universidades de los EE. UU. y el Reino Unido. El objetivo de la alianza es realizar investigaciones básicas en apoyo de las operaciones centradas en redes que cubran las necesidades de ambas naciones.

En 2009, el Ejército de los EE. UU. formó la Network Science CTA , una alianza de investigación colaborativa entre el Laboratorio de Investigación del Ejército , CERDEC y un consorcio de alrededor de 30 laboratorios de investigación y desarrollo industriales y universidades en los EE. UU. El objetivo de la alianza es desarrollar una comprensión profunda de los puntos en común subyacentes entre las redes sociales/cognitivas, de información y de comunicaciones entrelazadas y, como resultado, mejorar nuestra capacidad para analizar, predecir, diseñar e influir en sistemas complejos que entrelazan muchos tipos de redes.

Posteriormente, como resultado de estos esfuerzos, el Departamento de Defensa de EE. UU. ha patrocinado numerosos proyectos de investigación que apoyan la Ciencia de Redes.

Clasificación de redes

Red determinista

La definición de red determinista se define en comparación con la definición de red probabilística. En las redes deterministas no ponderadas, las aristas existen o no; por lo general, usamos 0 para representar la inexistencia de una arista y 1 para representar su existencia. En las redes deterministas ponderadas, el valor de la arista representa el peso de cada arista, por ejemplo, el nivel de fuerza.

Red probabilística

En las redes probabilísticas, los valores detrás de cada arista representan la probabilidad de existencia de cada arista. Por ejemplo, si una arista tiene un valor igual a 0,9, decimos que la probabilidad de existencia de esta arista es 0,9. ^[12]

Propiedades de red

A menudo, las redes tienen ciertos atributos que se pueden calcular para analizar las propiedades y características de la red. El comportamiento de estas propiedades de red a menudo define modelos de red y se puede utilizar para analizar cómo ciertos modelos contrastan entre sí. Muchas de las definiciones de otros términos utilizados en la ciencia de redes se pueden encontrar en el Glosario de teoría de grafos .

Tamaño

El tamaño de una red puede referirse al número de nodos o, menos comúnmente, al número de aristas que (para grafos conectados sin aristas múltiples) puede variar desde (un árbol) hasta (un grafo completo). En el caso de un grafo simple (una red en la que existe como máximo una arista (no dirigida) entre cada par de vértices, y en la que ningún vértice se conecta a sí mismo), tenemos ; para grafos dirigidos (sin nodos autoconectados), ; para grafos dirigidos con autoconexiones permitidas, . En la circunstancia de un grafo dentro del cual pueden existir múltiples aristas entre un par de vértices, . ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle N-1}$ ${\displaystyle E_{\max }}$ ${\displaystyle E_{\max }={\tbinom {N}{2}}=N(N-1)/2}$ ${\displaystyle E_{\max }=N(N-1)}$ ${\displaystyle E_{\max }=N^{2}}$ ${\displaystyle E_{\max }=\infty }$

Densidad

La densidad de una red se define como una relación normalizada entre 0 y 1 del número de aristas respecto del número de aristas posibles en una red con nodos. La densidad de red es una medida del porcentaje de aristas "opcionales" que existen en la red y se puede calcular como donde y son el número mínimo y máximo de aristas en una red conectada con nodos, respectivamente. En el caso de grafos simples, se da por el coeficiente binomial y , dando como resultado la densidad . Otra ecuación posible es mientras que los lazos son unidireccionales (Wasserman y Faust 1994). ^[13] Esto da una mejor visión general de la densidad de la red, porque se pueden medir las relaciones unidireccionales. ${\displaystyle D}$ ${\displaystyle E}$ ${\displaystyle N}$ ${\displaystyle D={\frac {E-E_{\mathrm {min} }}{E_{\mathrm {max} }-E_{\mathrm {min} }}}}$ ${\displaystyle E_{\mathrm {min} }}$ ${\displaystyle E_{\mathrm {max} }}$ ${\displaystyle N}$ ${\displaystyle E_{\mathrm {max} }}$ ${\displaystyle {\tbinom {N}{2}}}$ ${\displaystyle E_{\mathrm {min} }=N-1}$ ${\displaystyle D={\frac {E-(N-1)}{E_{\mathrm {max} }-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}}$ ${\displaystyle D={\frac {T-2N+2}{N(N-3)+2}},}$ ${\displaystyle T}$

Densidad de red plana

La densidad de una red, donde no hay intersección entre aristas, se define como una relación entre el número de aristas y el número de aristas posibles en una red con nodos, dada por un gráfico sin aristas que se intersecan , dando ${\displaystyle D}$ ${\displaystyle E}$ ${\displaystyle N}$ ${\displaystyle (E_{\max }=3N-6)}$ ${\displaystyle D={\frac {E-N+1}{2N-5}}.}$

Grado medio

El grado de un nodo es el número de aristas conectadas a él. Estrechamente relacionado con la densidad de una red está el grado promedio (o, en el caso de grafos dirigidos, , el antiguo factor de 2 que surge de cada arista en un grafo no dirigido que contribuye al grado de dos vértices distintos). En el modelo de grafo aleatorio ER ( ) podemos calcular el valor esperado de (igual al valor esperado de de un vértice arbitrario): un vértice aleatorio tiene otros vértices en la red disponibles y con probabilidad , se conecta a cada uno. Por lo tanto, . ${\displaystyle k}$ ${\displaystyle \langle k\rangle ={\tfrac {2E}{N}}}$ ${\displaystyle \langle k\rangle ={\tfrac {E}{N}}}$ ${\displaystyle G(N,p)}$ ${\displaystyle \langle k\rangle }$ ${\displaystyle k}$ ${\displaystyle N-1}$ ${\displaystyle p}$ ${\displaystyle \mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)}$

Longitud de ruta más corta promedio (o longitud de ruta característica)

La longitud media de la ruta más corta se calcula encontrando la ruta más corta entre todos los pares de nodos y tomando el promedio de todas las rutas de la longitud de la misma (la longitud es el número de aristas intermedias contenidas en la ruta, es decir, la distancia entre los dos vértices dentro del grafo). Esto nos muestra, en promedio, el número de pasos que se necesitan para llegar de un miembro de la red a otro. El comportamiento de la longitud media esperada de la ruta más corta (es decir, el promedio del conjunto de la longitud media de la ruta más corta) como una función del número de vértices de un modelo de red aleatoria define si ese modelo exhibe el efecto de mundo pequeño; si escala como , el modelo genera redes de mundo pequeño. Para un crecimiento más rápido que el logarítmico, el modelo no produce mundos pequeños. El caso especial de se conoce como efecto de mundo ultrapequeño. ${\displaystyle d_{u,v}}$ ${\displaystyle u,v}$ ${\displaystyle N}$ ${\displaystyle O(\ln N)}$ ${\displaystyle O(\ln \ln N)}$

Diámetro de una red

Como otro medio para medir los gráficos de red, podemos definir el diámetro de una red como el más largo de todos los caminos más cortos calculados en una red. Es la distancia más corta entre los dos nodos más distantes de la red. En otras palabras, una vez que se calcula la longitud del camino más corto desde cada nodo a todos los demás nodos, el diámetro es el más largo de todos los caminos calculados. El diámetro es representativo del tamaño lineal de una red. Si los nodos ABCD están conectados, yendo de A a D, este sería el diámetro de 3 (3 saltos, 3 enlaces). ^{[ cita requerida ]}

Coeficiente de agrupamiento

El coeficiente de agrupamiento es una medida de una propiedad del tipo "todos mis amigos se conocen entre sí". Esto a veces se describe como los amigos de mis amigos son mis amigos. Más precisamente, el coeficiente de agrupamiento de un nodo es la relación entre los enlaces existentes que conectan a los vecinos de un nodo entre sí y el número máximo posible de dichos enlaces. El coeficiente de agrupamiento para toda la red es el promedio de los coeficientes de agrupamiento de todos los nodos. Un coeficiente de agrupamiento alto para una red es otro indicio de un mundo pequeño .

El coeficiente de agrupamiento del nodo 'ésimo es ${\displaystyle i}$

${\displaystyle C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,}$

donde es el número de vecinos del nodo 'ésimo, y es el número de conexiones entre estos vecinos. El número máximo posible de conexiones entre vecinos es, entonces, ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle e_{i}}$

${\displaystyle {\binom {k}{2}}={{k(k-1)} \over 2}\,.}$

Desde un punto de vista probabilístico, el coeficiente de agrupamiento local esperado es la probabilidad de que exista un vínculo entre dos vecinos arbitrarios del mismo nodo.

Conectividad

La forma en que se conecta una red juega un papel importante en la forma en que se analizan e interpretan las redes. Las redes se clasifican en cuatro categorías diferentes:

• Clique / Gráfico completo : red completamente conectada, donde todos los nodos están conectados entre sí. Estas redes son simétricas, ya que todos los nodos tienen enlaces de entrada y de salida con todos los demás.
• Componente gigante : un único componente conectado que contiene la mayoría de los nodos de la red.
• Componente débilmente conectado : una colección de nodos en la que existe una ruta desde cualquier nodo a cualquier otro, ignorando la direccionalidad de los bordes.
• Componente fuertemente conectado : una colección de nodos en la que existe una ruta dirigida desde cualquier nodo a cualquier otro.

Centralidad de nodos

Los índices de centralidad generan clasificaciones que buscan identificar los nodos más importantes en un modelo de red. Diferentes índices de centralidad codifican diferentes contextos para la palabra "importancia". La centralidad de intermediación , por ejemplo, considera que un nodo es muy importante si forma puentes entre muchos otros nodos. La centralidad de valor propio , por el contrario, considera que un nodo es muy importante si muchos otros nodos muy importantes se vinculan a él. Se han propuesto cientos de medidas de este tipo en la literatura.

Los índices de centralidad sólo son precisos para identificar los nodos más importantes. Las medidas rara vez, o nunca, son significativas para el resto de los nodos de la red. ^{[14] [15]} Además, sus indicaciones sólo son precisas dentro de su contexto supuesto de importancia, y tienden a "equivocarse" para otros contextos. ^[16] Por ejemplo, imaginemos dos comunidades separadas cuyo único vínculo es una arista entre el miembro más joven de cada comunidad. Dado que cualquier transferencia de una comunidad a la otra debe pasar por este vínculo, los dos miembros más jóvenes tendrán una centralidad de intermediación alta. Pero, dado que son jóvenes, (presumiblemente) tienen pocas conexiones con los nodos "importantes" de su comunidad, lo que significa que su centralidad de valor propio sería bastante baja.

Influencia del nodo

Las limitaciones de las medidas de centralidad han llevado al desarrollo de medidas más generales. Dos ejemplos son la accesibilidad , que utiliza la diversidad de recorridos aleatorios para medir la accesibilidad del resto de la red desde un nodo de inicio determinado, ^[17] y la fuerza esperada , derivada del valor esperado de la fuerza de infección generada por un nodo. ^[14] Ambas medidas se pueden calcular de forma significativa a partir de la estructura de la red únicamente.

Estructura de la comunidad

Fig. 1: Esbozo de una red pequeña que muestra la estructura de la comunidad , con tres grupos de nodos con conexiones internas densas y conexiones más dispersas entre grupos.

Los nodos de una red pueden dividirse en grupos que representan comunidades. Según el contexto, las comunidades pueden ser distintas o superpuestas. Normalmente, los nodos de dichas comunidades estarán fuertemente conectados con otros nodos de la misma comunidad, pero débilmente conectados con nodos fuera de la comunidad. En ausencia de una verdad fundamental que describa la estructura de la comunidad de una red específica, se han desarrollado varios algoritmos para inferir posibles estructuras de la comunidad utilizando métodos de agrupamiento supervisados ​​o no supervisados.

Modelos de red

Los modelos de red sirven como base para comprender las interacciones dentro de redes complejas empíricas. Varios modelos de generación de grafos aleatorios producen estructuras de red que pueden usarse en comparación con redes complejas del mundo real.

Modelo de gráfico aleatorio Erdős-Rényi

Este modelo de Erdős–Rényi se genera con N = 4 nodos. Para cada arista del grafo completo formado por todos los N nodos, se genera un número aleatorio y se compara con una probabilidad dada. Si el número aleatorio es menor que p , se forma una arista en el modelo.

El modelo Erdős–Rényi , llamado así por Paul Erdős y Alfréd Rényi , se utiliza para generar grafos aleatorios en los que se establecen aristas entre nodos con probabilidades iguales. Se puede utilizar en el método probabilístico para demostrar la existencia de grafos que satisfacen varias propiedades o para proporcionar una definición rigurosa de lo que significa que una propiedad se cumpla en casi todos los grafos.

Para generar un modelo Erdős–Rényi se deben especificar dos parámetros: el número total de nodos n y la probabilidad p de que un par aleatorio de nodos tenga una arista. ${\displaystyle G(n,p)}$

Debido a que el modelo se genera sin sesgo hacia nodos particulares, la distribución de grados es binomial: para un vértice elegido aleatoriamente , ${\displaystyle v}$

${\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.}$

En este modelo el coeficiente de agrupamiento es 0 a.s. El comportamiento de se puede dividir en tres regiones. ${\displaystyle G(n,p)}$

Subcrítico : Todos los componentes son simples y muy pequeños, el componente más grande tiene tamaño ; ${\displaystyle np<1}$ ${\displaystyle |C_{1}|=O(\log n)}$

Crítico : ; ${\displaystyle np=1}$ ${\displaystyle |C_{1}|=O(n^{\frac {2}{3}})}$

Supercrítico : donde es la solución positiva de la ecuación . ${\displaystyle np>1}$ ${\displaystyle |C_{1}|\approx yn}$ ${\displaystyle y=y(np)}$ ${\displaystyle e^{-pny}=1-y}$

El componente conectado más grande tiene una alta complejidad. Todos los demás componentes son simples y pequeños . ${\displaystyle |C_{2}|=O(\log n)}$

Modelo de configuración

El modelo de configuración toma una secuencia de grados ^{[18] [19]} o una distribución de grados ^[20] (que posteriormente se utiliza para generar una secuencia de grados) como entrada, y produce grafos conectados aleatoriamente en todos los aspectos excepto en la secuencia de grados. Esto significa que para una elección dada de la secuencia de grados, el grafo se elige de manera uniforme al azar del conjunto de todos los grafos que cumplen con esta secuencia de grados. El grado de un vértice elegido aleatoriamente es una variable aleatoria independiente e idénticamente distribuida con valores enteros. Cuando , el grafo de configuración contiene el componente conectado gigante , que tiene un tamaño infinito. ^[19] El resto de los componentes tienen tamaños finitos, que pueden cuantificarse con la noción de distribución de tamaño. La probabilidad de que un nodo muestreado aleatoriamente esté conectado a un componente de tamaño está dada por las potencias de convolución de la distribución de grados: ^[21] donde denota la distribución de grados y . El componente gigante puede destruirse eliminando aleatoriamente la fracción crítica de todos los bordes. Este proceso se llama percolación en redes aleatorias . Cuando el segundo momento de la distribución de grados es finito, , esta fracción de borde crítico está dada por ^[22] , y la distancia promedio vértice-vértice en el componente gigante escala logarítmicamente con el tamaño total de la red, . ^[20] ${\displaystyle k}$ ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$ ${\displaystyle w(n)}$ ${\displaystyle n}$ $${\displaystyle w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}}$$ ${\displaystyle u(k)}$ ${\displaystyle u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}}$ ${\displaystyle p_{c}}$ ${\textstyle \mathbb {E} [k^{2}]<\infty }$ ${\displaystyle p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}}$ ${\displaystyle l}$ ${\displaystyle l=O(\log N)}$

En el modelo de configuración dirigida, el grado de un nodo está dado por dos números, grado de entrada y grado de salida , y en consecuencia, la distribución de grados es de dos variables. El número esperado de aristas de entrada y de salida coincide, de modo que . El modelo de configuración dirigida contiene el componente gigante si y solo si ^[23] Nótese que y son iguales y, por lo tanto, intercambiables en la última desigualdad. La probabilidad de que un vértice elegido aleatoriamente pertenezca a un componente de tamaño está dada por: ^[24] para componentes de entrada, y ${\displaystyle k_{\text{in}}}$ ${\displaystyle k_{\text{out}}}$ ${\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$ $${\displaystyle 2\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}k_{\text{out}}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0.}$$ ${\textstyle \mathbb {E} [k_{\text{in}}]}$ ${\textstyle \mathbb {E} [k_{\text{out}}]}$ ${\displaystyle n}$ $${\displaystyle h_{\text{in}}(n)={\frac {\mathbb {E} [k_{in}]}{n-1}}{\tilde {u}}_{\text{in}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{in}}={\frac {k_{\text{in}}+1}{\mathbb {E} [k_{\text{in}}]}}\sum \limits _{k_{\text{out}}\geq 0}u(k_{\text{in}}+1,k_{\text{out}}),}$$

${\displaystyle h_{\text{out}}(n)={\frac {\mathbb {E} [k_{\text{out}}]}{n-1}}{\tilde {u}}_{\text{out}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{out}}={\frac {k_{\text{out}}+1}{\mathbb {E} [k_{\text{out}}]}}\sum \limits _{k_{\text{in}}\geq 0}u(k_{\text{in}},k_{\text{out}}+1),}$

Para componentes externos.

Modelo de mundo pequeño de Watts-Strogatz

El modelo de Watts y Strogatz utiliza el concepto de recableado para lograr su estructura. El generador de modelos itera a través de cada borde en la estructura reticular original. Un borde puede cambiar sus vértices conectados de acuerdo con una probabilidad de recableado dada. en este ejemplo. ${\displaystyle \langle k\rangle =4}$

El modelo de Watts y Strogatz es un modelo de generación de gráficos aleatorios que produce gráficos con propiedades de mundo pequeño .

Se utiliza una estructura reticular inicial para generar un modelo de Watts-Strogatz. Cada nodo de la red está vinculado inicialmente a sus vecinos más cercanos. Se especifica otro parámetro como la probabilidad de recableado. Cada borde tiene una probabilidad de que se recablee al gráfico como un borde aleatorio. El número esperado de enlaces recableados en el modelo es . ${\displaystyle \langle k\rangle }$ ${\displaystyle p}$ ${\displaystyle pE=pN\langle k\rangle /2}$

Como el modelo de Watts-Strogatz comienza como una estructura reticular no aleatoria, tiene un coeficiente de agrupamiento muy alto junto con una longitud de ruta promedio alta. Es probable que cada recableado cree un atajo entre grupos altamente conectados. A medida que aumenta la probabilidad de recableado, el coeficiente de agrupamiento disminuye más lentamente que la longitud de ruta promedio. En efecto, esto permite que la longitud de ruta promedio de la red disminuya significativamente con solo pequeñas disminuciones en el coeficiente de agrupamiento. Los valores más altos de p fuerzan más bordes recableados, lo que en efecto convierte al modelo de Watts-Strogatz en una red aleatoria.

Modelo de apego preferencial de Barabási-Albert (BA)

El modelo de Barabási-Albert es un modelo de red aleatoria que se utiliza para demostrar una vinculación preferencial o un efecto de "los ricos se hacen más ricos". En este modelo, es más probable que una arista se una a los nodos con grados más altos. La red comienza con una red inicial de m ₀ nodos. m ₀  ≥ 2 y el grado de cada nodo en la red inicial debe ser al menos 1, de lo contrario, siempre permanecerá desconectado del resto de la red.

En el modelo BA, los nuevos nodos se agregan a la red de a uno por vez. Cada nuevo nodo se conecta a los nodos existentes con una probabilidad proporcional a la cantidad de enlaces que ya tienen los nodos existentes. Formalmente, la probabilidad p _i de que el nuevo nodo esté conectado al nodo i es ^[25] ${\displaystyle m}$

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

donde k _i es el grado del nodo i . Los nodos fuertemente enlazados ("centros") tienden a acumular rápidamente aún más enlaces, mientras que los nodos con sólo unos pocos enlaces tienen pocas probabilidades de ser elegidos como destino para un nuevo enlace. Los nuevos nodos tienen una "preferencia" por unirse a los nodos que ya están fuertemente enlazados.

Distribución de grados del modelo BA, que sigue una ley de potencia. En escala logarítmica, la función de ley de potencia es una línea recta. ^[26]

La distribución de grados resultante del modelo BA no tiene escala, en particular, para grados grandes es una ley de potencia de la forma:

${\displaystyle P(k)\sim k^{-3}\,}$

Los nodos presentan una alta centralidad de intermediación, lo que permite que existan rutas cortas entre nodos. Como resultado, el modelo BA tiende a tener longitudes de ruta promedio muy cortas. El coeficiente de agrupamiento de este modelo también tiende a ser 0.

El modelo Barabási–Albert ^[26] fue desarrollado para redes no dirigidas, con el objetivo de explicar la universalidad de la propiedad de no tener escala, y se aplicó a una amplia gama de redes y aplicaciones diferentes. La versión dirigida de este modelo es el modelo Price ^{[27] [28]} , que fue desarrollado solo para redes de citas.

Fijación preferencial no lineal

En la conexión preferencial no lineal (NLPA), los nodos existentes en la red obtienen nuevos bordes proporcionalmente al grado del nodo elevado a una potencia positiva constante, . ^[29] Formalmente, esto significa que la probabilidad de que el nodo gane un nuevo borde está dada por ${\displaystyle \alpha }$ ${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}}.}$

Si , NLPA se reduce al modelo BA y se denomina "lineal". Si , NLPA se denomina "sublineal" y la distribución de grados de la red tiende a una distribución exponencial estirada . Si , NLPA se denomina "superlineal" y una pequeña cantidad de nodos se conectan a casi todos los demás nodos de la red. Para ambos y , la propiedad de libertad de escala de la red se rompe en el límite del tamaño infinito del sistema. Sin embargo, si es solo ligeramente mayor que , NLPA puede dar como resultado distribuciones de grados que parecen ser transitoriamente libres de escala. ^[30] ${\displaystyle \alpha =1}$ ${\displaystyle 0<\alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha }$ ${\displaystyle 1}$

Modelo de apego impulsado por la mediación (MDA)

En el modelo de conexión impulsado por mediación (MDA), en el que un nuevo nodo que llega con aristas elige un nodo conectado existente al azar y luego se conecta no con ese sino con uno de sus vecinos elegidos también al azar. La probabilidad de que el nodo del nodo existente elegido sea ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle \Pi (i)}$ ${\displaystyle i}$

${\displaystyle \Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.}$

El factor es el inverso de la media armónica (IHM) de los grados de los vecinos de un nodo . Una amplia investigación numérica sugiere que para un valor de IHM medio aproximado en el límite grande se convierte en una constante que significa . Esto implica que cuanto mayores sean los enlaces (grado) que tenga un nodo, mayor será su probabilidad de obtener más enlaces, ya que se puede llegar a ellos de una mayor cantidad de formas a través de mediadores, lo que esencialmente encarna la idea intuitiva del mecanismo de los ricos se hacen más ricos (o la regla de unión preferencial del modelo de Barabasi-Albert). Por lo tanto, se puede ver que la red MDA sigue la regla de PA pero disfrazada. ^[31] ${\displaystyle {\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle m>14}$ ${\displaystyle N}$ ${\displaystyle \Pi (i)\propto k_{i}}$

Sin embargo, como se describe el mecanismo del ganador se lo lleva todo, encontramos que casi la totalidad de los nodos tienen grado uno y uno es súper rico en grado. A medida que el valor aumenta, la disparidad entre los súper ricos y los pobres disminuye y encontramos una transición del mecanismo de los ricos que se vuelven súper ricos al de los ricos que se vuelven más ricos. ${\displaystyle m=1}$ ${\displaystyle 99\%}$ ${\displaystyle m}$ ${\displaystyle m>14}$

Modelo de fitness

Caldarelli et al. han introducido otro modelo en el que el ingrediente clave es la naturaleza del vértice. ^[32] En este caso, se crea un vínculo entre dos vértices con una probabilidad dada por una función de enlace de las aptitudes de los vértices involucrados. El grado de un vértice i viene dado por ^[33]. ${\displaystyle i,j}$ ${\displaystyle f(\eta _{i},\eta _{j})}$

${\displaystyle k(\eta _{i})=N\int _{0}^{\infty }f(\eta _{i},\eta _{j})\rho (\eta _{j})\,d\eta _{j}}$

Si es una función invertible y creciente de , entonces la distribución de probabilidad está dada por ${\displaystyle k(\eta _{i})}$ ${\displaystyle \eta _{i}}$ ${\displaystyle P(k)}$

${\displaystyle P(k)=\rho (\eta (k))\cdot \eta '(k)}$

En consecuencia, si las aptitudes se distribuyen como una ley de potencia, entonces el grado del nodo también lo hace. ${\displaystyle \eta }$

De manera menos intuitiva, con una distribución de probabilidad de rápida descomposición junto con una función de enlace del tipo ${\displaystyle \rho (\eta )=e^{-\eta }}$

${\displaystyle f(\eta _{i},\eta _{j})=\Theta (\eta _{i}+\eta _{j}-Z)}$

con una constante y la función Heavyside, también obtenemos redes libres de escala. ${\displaystyle Z}$ ${\displaystyle \Theta }$

Este modelo se ha aplicado con éxito para describir el comercio entre naciones utilizando el PIB como aptitud para los diversos nodos y una función de enlace del tipo ^{[34] [35]} ${\displaystyle i,j}$

${\displaystyle {\frac {\delta \eta _{i}\eta _{j}}{1+\delta \eta _{i}\eta _{j}}}.}$

Modelos de gráficos aleatorios exponenciales

Los modelos de gráficos aleatorios exponenciales (ERGM) son una familia de modelos estadísticos para analizar datos de redes sociales y de otro tipo. ^[36] La familia exponencial es una amplia familia de modelos que abarcan muchos tipos de datos, no solo redes. Un ERGM es un modelo de esta familia que describe redes.

Adoptamos la notación para representar un gráfico aleatorio a través de un conjunto de nodos y una colección de variables de enlace , indexadas por pares de nodos , donde si los nodos están conectados por un borde y en caso contrario. ${\displaystyle Y\in {\mathcal {Y}}}$ ${\displaystyle n}$ ${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$ ${\displaystyle ij}$ ${\displaystyle Y_{ij}=1}$ ${\displaystyle (i,j)}$ ${\displaystyle Y_{ij}=0}$

El supuesto básico de los ERGM es que la estructura de un grafo observado puede explicarse mediante un vector dado de estadísticas suficientes que son una función de la red observada y, en algunos casos, de los atributos nodales. La probabilidad de un grafo en un ERGM se define mediante: ${\displaystyle y}$ ${\displaystyle s(y)}$ ${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}}$

donde es un vector de parámetros del modelo asociado con y es una constante normalizadora. ${\displaystyle \theta }$ ${\displaystyle s(y)}$ ${\displaystyle c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))}$

Análisis de red

Análisis de redes sociales

El análisis de redes sociales examina la estructura de las relaciones entre entidades sociales. ^[37] Estas entidades suelen ser personas, pero también pueden ser grupos , organizaciones , estados nacionales , sitios web y publicaciones académicas .

Desde la década de 1970, el estudio empírico de las redes ha desempeñado un papel central en las ciencias sociales, y muchas de las herramientas matemáticas y estadísticas utilizadas para estudiar las redes se han desarrollado por primera vez en sociología . ^[38] Entre muchas otras aplicaciones, el análisis de redes sociales se ha utilizado para comprender la difusión de innovaciones , ^[39] noticias y rumores. De manera similar, se ha utilizado para examinar la propagación de enfermedades y comportamientos relacionados con la salud . También se ha aplicado al estudio de los mercados , donde se ha utilizado para examinar el papel de la confianza en las relaciones de intercambio y de los mecanismos sociales en la fijación de precios. De manera similar, se ha utilizado para estudiar el reclutamiento en movimientos políticos y organizaciones sociales. También se ha utilizado para conceptualizar los desacuerdos científicos, así como el prestigio académico. En la literatura sobre la adquisición de una segunda lengua, tiene una historia establecida en la investigación de estudios en el extranjero, revelando cómo las redes de interacción entre pares influyen en su progreso lingüístico. ^[40] Más recientemente, el análisis de redes (y su primo cercano, el análisis de tráfico ) ha ganado un uso significativo en inteligencia militar, para descubrir redes insurgentes de naturaleza tanto jerárquica como sin líder . ^{[41] [42]} En criminología , se está utilizando para identificar actores influyentes en bandas criminales, movimientos de delincuentes, co-delincuencia, predecir actividades criminales y formular políticas. ^[43]

Análisis de red dinámica

El análisis de redes dinámicas examina la estructura cambiante de las relaciones entre diferentes clases de entidades en sistemas sociotécnicos complejos y refleja la estabilidad social y los cambios como el surgimiento de nuevos grupos, temas y líderes. ^{[44] [45] [46]} El análisis de redes dinámicas se centra en metarredes compuestas por múltiples tipos de nodos (entidades) y múltiples tipos de enlaces . Estas entidades pueden ser muy variadas. Los ejemplos incluyen personas, organizaciones, temas, recursos, tareas, eventos, ubicaciones y creencias.

Las técnicas de redes dinámicas son particularmente útiles para evaluar tendencias y cambios en las redes a lo largo del tiempo, identificar líderes emergentes y examinar la coevolución de personas e ideas.

Análisis de redes biológicas

Con la reciente explosión de datos biológicos de alto rendimiento disponibles públicamente, el análisis de redes moleculares ha ganado un interés significativo. El tipo de análisis en este contenido está estrechamente relacionado con el análisis de redes sociales, pero a menudo se centra en patrones locales en la red. Por ejemplo, los motivos de red son pequeños subgrafos que están sobrerrepresentados en la red. Los motivos de actividad son patrones sobrerrepresentados similares en los atributos de los nodos y los bordes de la red que están sobrerrepresentados dada la estructura de la red. El análisis de redes biológicas ha llevado al desarrollo de la medicina de redes , que analiza el efecto de las enfermedades en el interactoma . ^[47]

Análisis de redes semánticas

El análisis de redes semánticas es un subcampo del análisis de redes que se centra en las relaciones entre palabras y conceptos en una red. Las palabras se representan como nodos y su proximidad o coocurrencia en el texto se representan como bordes. Por lo tanto, las redes semánticas son representaciones gráficas del conocimiento y se utilizan comúnmente en aplicaciones de neurolingüística y procesamiento del lenguaje natural . El análisis de redes semánticas también se utiliza como método para analizar textos extensos e identificar los temas y tópicos principales (por ejemplo, de publicaciones en redes sociales ), para revelar sesgos (por ejemplo, en la cobertura de noticias) o incluso para mapear un campo de investigación completo. ^[48]

Análisis de enlaces

El análisis de vínculos es un subconjunto del análisis de redes que explora las asociaciones entre objetos. Un ejemplo puede ser el examen de las direcciones de sospechosos y víctimas, los números de teléfono que han marcado y las transacciones financieras en las que han participado durante un período de tiempo determinado, y las relaciones familiares entre estos sujetos como parte de una investigación policial. El análisis de vínculos en este caso proporciona las relaciones y asociaciones cruciales entre muchos objetos de diferentes tipos que no son evidentes a partir de piezas de información aisladas. El análisis de vínculos asistido por computadora o totalmente automático basado en computadora es cada vez más utilizado por los bancos y las agencias de seguros en la detección de fraudes , por los operadores de telecomunicaciones en el análisis de redes de telecomunicaciones, por el sector médico en epidemiología y farmacología , en investigaciones policiales , por los motores de búsqueda para la clasificación de relevancia (y, a la inversa, por los spammers para la indexación de spam y por los propietarios de empresas para la optimización de motores de búsqueda ) y en cualquier otro lugar donde se deban analizar las relaciones entre muchos objetos.

Análisis de la pandemia

El modelo SIR es uno de los algoritmos más conocidos para predecir la propagación de pandemias globales dentro de una población infecciosa.

Susceptible a infecciones

${\displaystyle S=\beta \left({\frac {1}{N}}\right)}$

La fórmula anterior describe la "fuerza" de infección para cada unidad susceptible en una población infecciosa, donde β es equivalente a la tasa de transmisión de dicha enfermedad.

Para rastrear el cambio de personas susceptibles en una población infecciosa:

${\displaystyle \Delta S=\beta \times S{1 \over N}\,\Delta t}$

De infectado a recuperado

${\displaystyle \Delta I=\mu I\,\Delta t}$

Con el tiempo, el número de personas infectadas fluctúa según: la tasa de recuperación especificada, representada por pero deducida a uno durante el período infeccioso promedio , el número de individuos infecciosos, y el cambio en el tiempo, . ${\displaystyle \mu }$ ${\displaystyle {1 \over \tau }}$ ${\displaystyle I}$ ${\displaystyle \Delta t}$

Periodo infeccioso

Si una población será superada por una pandemia, con respecto al modelo SIR, depende del valor de "la cantidad promedio de personas infectadas por un individuo infectado". ${\displaystyle R_{0}}$

${\displaystyle R_{0}=\beta \tau ={\beta \over \mu }}$

Análisis de enlaces web

Varios algoritmos de clasificación de búsquedas web utilizan métricas de centralidad basadas en enlaces, incluidos (en orden de aparición) Hyper Search de Marchiori , PageRank de Google , el algoritmo HITS de Kleinberg , los algoritmos CheiRank y TrustRank . El análisis de enlaces también se lleva a cabo en las ciencias de la información y la comunicación para comprender y extraer información de la estructura de colecciones de páginas web. Por ejemplo, el análisis podría ser de la interconexión entre los sitios web o blogs de políticos.

PageRank

PageRank funciona seleccionando aleatoriamente "nodos" o sitios web y luego, con una cierta probabilidad, "saltando aleatoriamente" a otros nodos. Al saltar aleatoriamente a estos otros nodos, ayuda a PageRank a recorrer completamente la red, ya que algunas páginas web existen en la periferia y no se evaluarían tan fácilmente.

Cada nodo, , tiene un PageRank definido por la suma de páginas que enlazan a multiplicado por uno los enlaces salientes o "grado de salida" de multiplicado por la "importancia" o PageRank de . ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j}$

${\displaystyle x_{i}=\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}}$

Salto aleatorio

Como se explicó anteriormente, PageRank utiliza saltos aleatorios para intentar asignar PageRank a todos los sitios web de Internet. Estos saltos aleatorios encuentran sitios web que no se encontrarían con las metodologías de búsqueda normales, como la búsqueda en amplitud y la búsqueda en profundidad .

Una mejora con respecto a la fórmula antes mencionada para determinar el PageRank incluye la incorporación de estos componentes de salto aleatorio. Sin los saltos aleatorios, algunas páginas recibirían un PageRank de 0, lo que no sería bueno.

El primero es , o la probabilidad de que ocurra un salto aleatorio. En contraste está el "factor de amortiguación", o . ${\displaystyle \alpha }$ ${\displaystyle 1-\alpha }$

${\displaystyle R{(p)}={\alpha \over N}+(1-\alpha )\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}}$

Otra forma de verlo:

${\displaystyle R(A)=\sum {R_{B} \over B_{\text{(outlinks)}}}+\cdots +{R_{n} \over n_{\text{(outlinks)}}}}$

Medidas de centralidad

La información sobre la importancia relativa de los nodos y los bordes de un grafo se puede obtener a través de medidas de centralidad , ampliamente utilizadas en disciplinas como la sociología . Las medidas de centralidad son esenciales cuando un análisis de red tiene que responder a preguntas como: "¿Qué nodos de la red deben ser el objetivo para garantizar que un mensaje o información se propague a todos o la mayoría de los nodos de la red?" o, por el contrario, "¿Qué nodos deben ser el objetivo para reducir la propagación de una enfermedad?". Las medidas de centralidad establecidas formalmente son la centralidad de grado , la centralidad de cercanía , la centralidad de intermediación , la centralidad de vector propio y la centralidad de Katz . El objetivo del análisis de red generalmente determina el tipo de medida(s) de centralidad que se utilizará. ^[37]

• La centralidad de grado de un nodo en una red es el número de enlaces (vértices) incidentes en el nodo.
• La centralidad de cercanía determina qué tan "cerca" está un nodo de otros nodos de una red midiendo la suma de las distancias más cortas (rutas geodésicas) entre ese nodo y todos los demás nodos de la red.
• La centralidad de intermediación determina la importancia relativa de un nodo midiendo la cantidad de tráfico que fluye a través de ese nodo hacia otros nodos de la red. Esto se hace midiendo la fracción de rutas que conectan todos los pares de nodos y que contienen el nodo de interés. La centralidad de intermediación de grupo mide la cantidad de tráfico que fluye a través de un grupo de nodos.
• La centralidad de vectores propios es una versión más sofisticada de la centralidad de grado, en la que la centralidad de un nodo no solo depende de la cantidad de enlaces que inciden en el nodo, sino también de la calidad de esos enlaces. Este factor de calidad está determinado por los vectores propios de la matriz de adyacencia de la red.
• La centralidad de Katz de un nodo se mide sumando las rutas geodésicas entre ese nodo y todos los nodos (alcanzables) de la red. Estas rutas están ponderadas; las rutas que conectan el nodo con sus vecinos inmediatos tienen pesos más altos que las que conectan con nodos más alejados de los vecinos inmediatos.

Difusión de contenidos en redes

El contenido de una red compleja se puede propagar mediante dos métodos principales: propagación conservada y propagación no conservada. ^[49] En la propagación conservada, la cantidad total de contenido que entra en una red compleja permanece constante a medida que pasa a través de ella. El modelo de propagación conservada se puede representar mejor con una jarra que contiene una cantidad fija de agua que se vierte en una serie de embudos conectados por tubos. Aquí, la jarra representa la fuente original y el agua es el contenido que se está propagando. Los embudos y los tubos de conexión representan los nodos y las conexiones entre nodos, respectivamente. A medida que el agua pasa de un embudo a otro, desaparece instantáneamente del embudo que anteriormente estaba expuesto al agua. En la propagación no conservada, la cantidad de contenido cambia a medida que entra y pasa a través de una red compleja. El modelo de propagación no conservada se puede representar mejor con un grifo que funciona continuamente y pasa por una serie de embudos conectados por tubos. Aquí, la cantidad de agua de la fuente original es infinita. Además, todos los embudos que han estado expuestos al agua continúan recibiendo el agua incluso cuando pasa a embudos sucesivos. El modelo no conservado es el más adecuado para explicar la transmisión de la mayoría de las enfermedades infecciosas .

El modelo SIR

En 1927, WO Kermack y AG McKendrick crearon un modelo en el que consideraron una población fija con solo tres compartimentos, susceptibles: , infectados , y recuperados, . Los compartimentos utilizados para este modelo constan de tres clases: ${\displaystyle S(t)}$ ${\displaystyle I(t)}$ ${\displaystyle R(t)}$

• ${\displaystyle S(t)}$Se utiliza para representar el número de individuos que aún no están infectados con la enfermedad en el momento t, o aquellos susceptibles a la enfermedad.
• ${\displaystyle I(t)}$denota el número de individuos que han sido infectados con la enfermedad y son capaces de transmitirla a aquellos en la categoría susceptible
• ${\displaystyle R(t)}$Es el compartimento que se utiliza para aquellas personas que han sido infectadas y luego se han recuperado de la enfermedad. Las personas en esta categoría no pueden volver a infectarse ni transmitir la infección a otras personas.

El flujo de este modelo puede considerarse de la siguiente manera:

${\displaystyle {\mathcal {S}}\rightarrow {\mathcal {I}}\rightarrow {\mathcal {R}}}$

Utilizando una población fija , Kermack y McKendrick derivaron las siguientes ecuaciones: ${\displaystyle N=S(t)+I(t)+R(t)}$

${\displaystyle {\begin{aligned}{\frac {dS}{dt}}&=-\beta SI\\[8pt]{\frac {dI}{dt}}&=\beta SI-\gamma I\\[8pt]{\frac {dR}{dt}}&=\gamma I\end{aligned}}}$

Se hicieron varias suposiciones en la formulación de estas ecuaciones: primero, un individuo en la población debe considerarse como teniendo una probabilidad igual a cualquier otro individuo de contraer la enfermedad con una tasa de , que se considera la tasa de contacto o infección de la enfermedad. Por lo tanto, un individuo infectado hace contacto y es capaz de transmitir la enfermedad con otros por unidad de tiempo y la fracción de contactos de un infectado con un susceptible es . El número de nuevas infecciones en unidad de tiempo por infectivo entonces es , dando la tasa de nuevas infecciones (o aquellos que salen de la categoría susceptible) como (Brauer y Castillo-Chavez, 2001). Para la segunda y tercera ecuaciones, considere la población que sale de la clase susceptible como igual al número que entra en la clase infectada. Sin embargo, los infectivos abandonan esta clase por unidad de tiempo para entrar en la clase recuperada/eliminada a una tasa por unidad de tiempo (donde representa la tasa media de recuperación, o el periodo medio infectivo). Estos procesos que ocurren simultáneamente se conocen como la Ley de Acción de Masas , una idea ampliamente aceptada que sostiene que la tasa de contacto entre dos grupos de una población es proporcional al tamaño de cada uno de los grupos involucrados (Daley y Gani, 2005). Finalmente, se supone que la tasa de infección y recuperación es mucho más rápida que la escala temporal de nacimientos y muertes y, por lo tanto, estos factores se ignoran en este modelo. ${\displaystyle \beta }$ ${\displaystyle \beta N}$ ${\displaystyle S/N}$ ${\displaystyle \beta N(S/N)}$ ${\displaystyle \beta N(S/N)I=\beta SI}$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle 1/\gamma }$

Se puede leer más sobre este modelo en la página del modelo de epidemia .

El enfoque de la ecuación maestra

Una ecuación maestra puede expresar el comportamiento de una red de crecimiento no dirigido donde, en cada paso de tiempo, se añade un nuevo nodo a la red, vinculado a un nodo antiguo (elegido aleatoriamente y sin preferencia). La red inicial está formada por dos nodos y dos enlaces entre ellos en el momento , esta configuración es necesaria solo para simplificar los cálculos posteriores, por lo que en el momento la red tiene nodos y enlaces. ${\displaystyle t=2}$ ${\displaystyle t=n}$ ${\displaystyle n}$ ${\displaystyle n}$

La ecuación maestra para esta red es:

${\displaystyle p(k,s,t+1)={\frac {1}{t}}p(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p(k,s,t),}$

donde es la probabilidad de tener el nodo con grado en el momento , y es el paso de tiempo en el que este nodo se agregó a la red. Tenga en cuenta que solo hay dos formas de que un nodo antiguo tenga enlaces en el momento : ${\displaystyle p(k,s,t)}$ ${\displaystyle s}$ ${\displaystyle k}$ ${\displaystyle t+1}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle k}$ ${\displaystyle t+1}$

• El nodo tiene grado en el tiempo y será vinculado por el nuevo nodo con probabilidad. ${\displaystyle s}$ ${\displaystyle k-1}$ ${\displaystyle t}$ ${\displaystyle 1/t}$
• Ya tiene título en este momento y no será vinculado por el nuevo nodo. ${\displaystyle k}$ ${\displaystyle t}$

Después de simplificar este modelo, la distribución de grados es ^[50] ${\displaystyle P(k)=2^{-k}.}$

A partir de esta red en crecimiento, se desarrolla un modelo de epidemia siguiendo una regla sencilla: cada vez que se añade un nuevo nodo y tras elegir el antiguo nodo con el que se quiere conectar, se toma una decisión: si este nuevo nodo se infectará o no. La ecuación maestra de este modelo de epidemia es:

${\displaystyle p_{r}(k,s,t)=r_{t}{\frac {1}{t}}p_{r}(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p_{r}(k,s,t),}$

donde representa la decisión de infectar ( ) o no ( ). Resolviendo esta ecuación maestra se obtiene la siguiente solución: ^[51] ${\displaystyle r_{t}}$ ${\displaystyle r_{t}=1}$ ${\displaystyle r_{t}=0}$ ${\displaystyle {\tilde {P}}_{r}(k)=\left({\frac {r}{2}}\right)^{k}.}$

Redes multicapa

Las redes multicapa son redes con múltiples tipos de relaciones. ^[52] Los intentos de modelar sistemas del mundo real como redes multidimensionales se han utilizado en varios campos, como el análisis de redes sociales, ^[53] la economía, la historia, el transporte urbano e internacional, la ecología, la psicología, la medicina, la biología, el comercio, la climatología, la física, la neurociencia computacional, la gestión de operaciones y las finanzas.

Optimización de la red

Los problemas de red que implican encontrar una forma óptima de hacer algo se estudian bajo el nombre de optimización combinatoria . Algunos ejemplos incluyen el flujo de red , el problema de la ruta más corta , el problema de transporte , el problema de transbordo , el problema de ubicación , el problema de emparejamiento , el problema de asignación , el problema de empaquetado , el problema de enrutamiento , el análisis de la ruta crítica y PERT (Técnica de evaluación y revisión de programas).

Redes interdependientes

Las redes interdependientes son redes en las que el funcionamiento de los nodos de una red depende del funcionamiento de los nodos de otra red. En la naturaleza, las redes rara vez aparecen de forma aislada, sino que suelen ser elementos de sistemas más grandes e interactúan con elementos de ese sistema complejo. Estas dependencias complejas pueden tener efectos no triviales entre sí. Un ejemplo bien estudiado es la interdependencia de las redes de infraestructura ^[54] , las centrales eléctricas que forman los nodos de la red eléctrica requieren combustible suministrado a través de una red de carreteras o tuberías y también se controlan a través de los nodos de la red de comunicaciones. Aunque la red de transporte no depende de la red eléctrica para funcionar, la red de comunicaciones sí lo hace. En estas redes de infraestructura, el mal funcionamiento de un número crítico de nodos, ya sea en la red eléctrica o en la red de comunicaciones, puede provocar fallos en cascada en todo el sistema con resultados potencialmente catastróficos para el funcionamiento de todo el sistema ^[55] . Si las dos redes se trataran de forma aislada, este importante efecto de retroalimentación no se observaría y las predicciones de la robustez de la red se sobrestimarían en gran medida.

Véase también

• Fallo en cascada
• El clima como redes complejas
• Red de innovación colaborativa
• Ecología comunicativa
• Red compleja
• Estructuras de núcleo-periferia en redes
• Evolución de dos fases
• Modelo de Erdős-Rényi
• Glosario de teoría de grafos
• Red de gradiente
• Teoría de categorías superiores
• Teoría de la red inmunitaria
• Guerra irregular
• Analizador de red
• Dinámica de red
• Formación de redes
• La teoría de redes en la evaluación de riesgos
• Topología de red
• Redes en la economía del trabajo
• Fijación preferencial no lineal
• Filtración
• Teoría de la percolación
• Análisis de redes de políticas
• Cortésmente
• Red cuántica compleja
• Redes aleatorias
• Rumor se extendió en redes sociales
• Redes sin escala
• Sistema dinámico secuencial
• Red de servicios
• Redes de mundo pequeño
• Corte estructural
• Teoría de sistemas

Referencias

1. Comité de Ciencias de Redes para Futuras Aplicaciones del Ejército (2006). Ciencias de Redes. Consejo Nacional de Investigación. doi :10.17226/11516. ISBN 978-0309653886.S2CID 196021177  .
2. Dénes Kőnig (1990). Teoría de gráficas finitas e infinitas (PDF) (PDF). Birkhäuser Boston. págs. 45–421. doi :10.1007/978-1-4684-8971-2. ISBN 978-1-4684-8971-2.
3. Moreno, Jacob Levy (23 de abril de 2009). ¿Quién sobrevivirá? Fundamentos de sociometría, psicoterapia de grupo y sociodrama . Beacon, NY: Beacon House (publicado en 1953).
4. "LAS EMOCIONES MAPEADAS POR LA NUEVA GEOGRAFÍA: LOS GRÁFICOS BUSCAN RETRATAR LAS CORRIENTES PSICOLÓGICAS DE LAS RELACIONES HUMANAS. LOS PRIMEROS ESTUDIOS EXHIBIERON LÍNEAS DE COLORES QUE MUESTRAN LOS GUSTOS Y LOS DESGRACIAS DE LOS INDIVIDUOS Y DE LOS GRUPOS. SE REVELAN MUCHOS DESADAPTADOS EL DR. JL MORENO CALCULA QUE HAY ENTRE 10 Y 15 MILLONES DE INDIVIDUOS AISLADOS EN LA NACIÓN". New York Times . 1933-04-17. p. 17 . Consultado el 26 de septiembre de 2024 .{{cite news}}: CS1 maint: url-status (link)
5. Krackhardt, David; Carley, Kathleen M. (junio de 1988). "Un modelo PCANS de estructura en la organización" (PDF) . Actas del Simposio Internacional de 1998 sobre Investigación y Tecnología de Mando y Control : 113–119.
6. Watts, Duncan J.; Strogatz, Steven H. (junio de 1998). "Dinámica colectiva de redes de 'mundo pequeño'". Nature . 393 (6684): 440–442. doi :10.1038/30918. ISSN  0028-0836.
7. Barabási, Albert-László; Albert, Réka (15 de octubre de 1999). "Aparición del escalamiento en redes aleatorias". Ciencia . 286 (5439): 509–512. doi : 10.1126/ciencia.286.5439.509. ISSN  0036-8075.
8. "Connected: El poder de seis grados (película para televisión, 2008) - IMDb". IMDb .
9. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.301.5111
10. "La ciencia de redes en West Point: los primeros años". YouTube .
11. https://www.westpoint.edu/academics/academic-departments/mathematical-sciences/network-science
12. Kollios, George (6 de diciembre de 2011). "Agrupamiento de grandes gráficos probabilísticos". IEEE Transactions on Knowledge and Data Engineering . 25 (2): 325–336. doi :10.1109/TKDE.2011.243. PMID  13188797. S2CID  5650233.
13. "APA PsycNet".
14. Lawyer, Glenn (marzo de 2015). "Entender el poder de propagación de todos los nodos de una red". Scientific Reports . 5 (O8665): 8665. arXiv : 1405.6707 . Bibcode :2015NatSR...5E8665L. doi :10.1038/srep08665. PMC 4345333 . PMID  25727453. 
15. Sikic, Mile; Lancic, Alen; Antulov-Fantulin, Nino; Stefancic, Hrvoje (octubre de 2013). "Centralidad epidémica: ¿se subestima el impacto epidémico de los nodos periféricos de la red?". European Physical Journal B . 86 (10): 440. arXiv : 1110.2558 . Bibcode :2013EPJB...86..440S. doi :10.1140/epjb/e2013-31025-5. S2CID  12052238.
16. Borgatti, Stephen P. (2005). "Centralidad y flujo de red". Redes sociales . 27 : 55–71. CiteSeerX 10.1.1.387.419 . doi :10.1016/j.socnet.2004.11.008. 
17. Travençolo, BAN; da F. Costa, L. (2008). "Accesibilidad en redes complejas". Physics Letters A . 373 (1): 89–95. Bibcode :2008PhLA..373...89T. doi :10.1016/j.physleta.2008.10.069.
18. Bender, Edward A; Canfield, E. Rodney (mayo de 1978). "El número asintótico de grafos etiquetados con secuencias de grado dadas". Journal of Combinatorial Theory, Serie A . 24 (3): 296–307. doi : 10.1016/0097-3165(78)90059-6 . ISSN  0097-3165.
19. Molloy, Michael; Reed, Bruce (marzo de 1995). "Un punto crítico para gráficos aleatorios con una secuencia de grados dada". Estructuras y algoritmos aleatorios . 6 (2–3): 161–180. CiteSeerX 10.1.1.24.6195 . doi :10.1002/rsa.3240060204. ISSN  1042-9832. 
20. Newman, MEJ; Strogatz, SH; Watts, DJ (24 de julio de 2001). "Gráficos aleatorios con distribuciones de grado arbitrario y sus aplicaciones". Physical Review E . 64 (2): 026118. arXiv : cond-mat/0007235 . Bibcode :2001PhRvE..64b6118N. doi :10.1103/PhysRevE.64.026118. PMID  11497662. S2CID  360112.
21. Kryven, Ivan (2017-05-02). "Expresión general para la distribución del tamaño de los componentes en redes de configuración infinita". Physical Review E . 95 (5): 052303. arXiv : 1703.05413 . Bibcode :2017PhRvE..95e2303K. doi :10.1103/PhysRevE.95.052303. PMID  28618550. S2CID  8421307.
22. Kryven, Ivan (1 de enero de 2018). "Resultados analíticos del modelo de grafo aleatorio de polimerización". Revista de química matemática . 56 (1): 140–157. arXiv : 1603.07154 . doi : 10.1007/s10910-017-0785-1 . ISSN  0259-9791.
23. Kryven, Ivan (27 de julio de 2016). "Aparición del componente débil gigante en grafos aleatorios dirigidos con distribuciones de grado arbitrario". Physical Review E . 94 (1): 012315. arXiv : 1607.03793 . Bibcode :2016PhRvE..94a2315K. doi :10.1103/PhysRevE.94.012315. PMID  27575156. S2CID  206251373.
24. Kryven, Ivan (2017-11-02). "Componentes finitos conectados en redes infinitas dirigidas y multiplexadas con distribuciones de grado arbitrario". Physical Review E . 96 (5): 052304. arXiv : 1709.04283 . Bibcode :2017PhRvE..96e2304K. doi :10.1103/PhysRevE.96.052304. PMID  29347790. S2CID  20741516.
25. R. Albert; A.-L. Barabási (2002). "Mecánica estadística de redes complejas" (PDF) . Reseñas de Física Moderna . 74 (1): 47–97. arXiv : cond-mat/0106096 . Bibcode :2002RvMP...74...47A. CiteSeerX 10.1.1.242.4753 . doi :10.1103/RevModPhys.74.47. S2CID  60545. Archivado desde el original (PDF) el 24 de agosto de 2015. 
26. Albert-László Barabási y Réka Albert (octubre de 1999). "Aparición del escalado en redes aleatorias" (PDF) . Ciencia . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Código Bib : 1999 Ciencia... 286.. 509B. doi : 10.1126/ciencia.286.5439.509. PMID  10521342. S2CID  524106. Archivado desde el original (PDF) el 17 de abril de 2012.
27. Price, Derek J. de Solla (30 de julio de 1965). "Redes de artículos científicos: el patrón de referencias bibliográficas indica la naturaleza del frente de investigación científica". Science . 149 (3683): ​​510–515. Bibcode :1965Sci...149..510D. doi :10.1126/science.149.3683.510. ISSN  0036-8075. PMID  14325149.
28. Price, Derek De Solla (1976). "Una teoría general de los procesos de ventaja acumulativa bibliométrica y de otro tipo". Revista de la Sociedad Americana de Ciencias de la Información . 27 (5): 292–306. doi :10.1002/asi.4630270505. S2CID  8536863.
29. Krapivsky, PL; Redner, S.; Leyvraz, F. (20 de noviembre de 2000). "Conectividad de redes aleatorias en crecimiento". Physical Review Letters . 85 (21): 4629–4632. arXiv : cond-mat/0005139 . Código Bibliográfico :2000PhRvL..85.4629K. doi :10.1103/PhysRevLett.85.4629. PMID  11082613. S2CID  16251662.
30. Krapivsky, Paul; Krioukov, Dmitri (21 de agosto de 2008). "Redes libres de escala como regímenes preasintóticos de unión preferencial superlineal". Physical Review E . 78 (2): 026114. arXiv : 0804.1366 . Bibcode :2008PhRvE..78b6114K. doi :10.1103/PhysRevE.78.026114. PMID  18850904. S2CID  14292535.
31. Hassan, MK; Islam, Liana; Arefinul Haque, Syed (marzo de 2017). "Distribución de grados, distribución de tamaño de rango y persistencia del liderazgo en redes de apego impulsadas por la mediación". Physica A . 469 : 23–30. arXiv : 1411.3444 . Bibcode :2017PhyA..469...23H. doi :10.1016/j.physa.2016.11.001. S2CID  51976352.
32. Caldarelli G., A. Capocci, P. De Los Rios, MA Muñoz, Physical Review Letters 89, 258702 (2002)
33. Servedio VDP, G. Caldarelli, P. Buttà, Revisión física E 70, 056126 (2004)
34. Garlaschelli D., MI Loffredo Cartas de revisión física 93, 188701 (2004)
35. Cimini G., T. Squartini, D. Garlaschelli y A. Gabrielli, Scientific Reports 5, 15758 (2015)
36. Lusher, Dean; Koskinen, Johan; Robins, Garry (2012). Modelos de gráficos aleatorios exponenciales para redes sociales: teoría, métodos y aplicaciones (Análisis estructural en las ciencias sociales) . doi :10.1017/CBO9780511894701. ISBN 9780521141383.OCLC 1120539699  .
37. Wasserman, Stanley y Katherine Faust. 1994. Análisis de redes sociales: métodos y aplicaciones. Cambridge: Cambridge University Press.
38. Newman, MEJ Networks: Una introducción. Oxford University Press. 2010, ISBN 978-0199206650 
39. Paradowski, Michał B.; Jonak, Lukasz (2012). "Difusión de la innovación lingüística como coordinación social". Psicología del Lenguaje y la Comunicación . 16 (2): 53–64. doi : 10.2478/v10057-012-0010-z .
40. Paradowski, Michał B.; Jarynowski, Andrzej; Jelińska, Magdalena; Czopek, Karolina (2021). "Las interacciones entre pares fuera de clase son importantes para la adquisición de una segunda lengua durante estancias breves en el extranjero: las contribuciones del análisis de redes sociales [Presentaciones de póster seleccionadas de la conferencia de la Asociación Estadounidense de Lingüística Aplicada, Denver, EE. UU., marzo de 2020]". Enseñanza de idiomas . 54 (1): 139–143. doi : 10.1017/S0261444820000580 .
41. "Hacia una comunidad de inteligencia adaptativa compleja. La wiki y el blog". D. Calvin Andrus . cia.gov. Archivado desde el original el 13 de junio de 2007 . Consultado el 25 de agosto de 2012 .
42. "Análisis de redes terroristas". Archivado desde el original el 23 de noviembre de 2012. Consultado el 12 de diciembre de 2011 .
43. PhD, Martin Bouchard; PhD, Aili Malm (2016-11-02). "Análisis de redes sociales y su contribución a la investigación sobre el delito y la justicia penal". Oxford Handbooks Online: Criminología y justicia penal . doi :10.1093/oxfordhb/9780199935383.013.21. ISBN 978-0-19-993538-3.
44. Gross, T. y Sayama, H. (Eds.). 2009. Redes adaptativas: teoría, modelos y aplicaciones. Springer.
45. Holme, P. y Saramäki, J. 2013. Redes temporales. Springer.
46. Xanthos, Aris, Pante, Isaac, Rochat, Yannick, Grandjean, Martin (2016). Visualizando la dinámica de las redes de personajes. En Humanidades digitales 2016: Universidad Jagellónica y Universidad Pedagógica, Cracovia, págs.
47. Barabási, AL; Gulbahce, N.; Loscalzo, J. (2011). "Medicina en red: un enfoque basado en redes para las enfermedades humanas". Nature Reviews Genetics . 12 (1): 56–68. doi :10.1038/nrg2918. PMC 3140052 . PMID  21164525. 
48. Segev, Elad (2022). Análisis de redes semánticas en las ciencias sociales. Londres: Routledge. ISBN 9780367636524Archivado del original el 5 de diciembre de 2021 . Consultado el 5 de diciembre de 2021 .
49. Newman, M., Barabási, A.-L., Watts, DJ [eds.] (2006) La estructura y dinámica de las redes. Princeton, Nueva Jersey: Princeton University Press.
50. Dorogovtsev, SN; Mendes, JFF (2003). Evolución de las redes: de las redes biológicas a Internet y la WWW . Nueva York, NY, EE. UU.: Oxford University Press, Inc. ISBN 978-0198515906.
51. Cotacallapa, M; Hase, MO (2016). "Epidemias en redes: un enfoque de ecuación maestra". Journal of Physics A . 49 (6): 065001. arXiv : 1604.01049 . Bibcode :2016JPhA...49f5001C. doi :10.1088/1751-8113/49/6/065001. S2CID  119206200.
52. De Domenico, Manlio (31 de marzo de 2022). Redes multicapa: análisis y visualización (1.ª ed.). Springer.
53. Rossi, Luca; Dickison, Mark E.; Magnani, Matteo (18 de julio de 2016). Redes sociales multicapa (1.ª ed.). Cambridge University Press.
54. "Identificación, comprensión y análisis de interdependencias críticas de infraestructura". Revista IEEE Control Systems . 21 (6): 11–25. Diciembre de 2001. doi :10.1109/37.969131.
55. Buldyrev, Sergey V.; et al. (abril de 2010). "Cascada catastrófica de fallos en redes interdependientes". Nature . 464 (7291): 1025–1028. arXiv : 0907.1182 . Bibcode :2010Natur.464.1025B. doi :10.1038/nature08932. PMID  20393559. S2CID  1836955.

Lectura adicional

• Un primer curso sobre ciencia de redes , F. Menczer , S. Fortunato, CA Davis (Cambridge University Press, 2020). ISBN 9781108471138. Sitio de GitHub con tutoriales, conjuntos de datos y otros recursos. 
• "Conectados: El poder de seis grados", https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Cohen, R.; Erez, K. (2000). "Resiliencia de Internet ante averías aleatorias". Phys. Rev. Lett . 85 (21): 4626–4628. arXiv : cond-mat/0007048 . Bibcode :2000PhRvL..85.4626C. CiteSeerX  10.1.1.242.6797 . doi :10.1103/physrevlett.85.4626. PMID  11082612. S2CID  15372152.
• Pu, Cun-Lai; Pei, Jiang; Michaelson, Andrew (2012). "Análisis de robustez de la controlabilidad de la red" (PDF) . Physica A . 391 (18): 4420–4425. Bibcode :2012PhyA..391.4420P. doi :10.1016/j.physa.2012.04.019. Archivado desde el original (PDF) el 2016-10-13 . Consultado el 2013-09-18 .
• SN Dorogovtsev y JFF Mendes, Evolución de las redes: de las redes biológicas a Internet y la WWW , Oxford University Press, 2003, ISBN 0-19-851590-1 
• Enlace: La nueva ciencia de las redes , A.-L. Barabási (Perseus Publishing, Cambridge)
• 'Redes sin escala' , G. Caldarelli (Oxford University Press, Oxford)
• Ciencia de redes , Comité de ciencia de redes para futuras aplicaciones del ejército, Consejo Nacional de Investigación. 2005. The National Academies Press (2005) ISBN 0-309-10026-7 
• Boletín de Ciencias de Redes , USMA (2007) ISBN 978-1-934808-00-9 
• La estructura y dinámica de las redes Mark Newman, Albert-László Barabási y Duncan J. Watts (The Princeton Press, 2006) ISBN 0-691-11357-2 
• Procesos dinámicos en redes complejas , Alain Barrat, Marc Barthelemy, Alessandro Vespignani (Cambridge University Press, 2008) ISBN 978-0-521-87950-7 
• Ciencia de redes: teoría y aplicaciones , Ted G. Lewis (Wiley, 11 de marzo de 2009) ISBN 0-470-33188-7 
• Nexus: pequeños mundos y la innovadora teoría de redes , Mark Buchanan (WW Norton & Company, junio de 2003) ISBN 0-393-32442-7 
• Six Degrees: La ciencia de una era conectada , Duncan J. Watts (WW Norton & Company, 17 de febrero de 2004) ISBN 0-393-32542-3