Modelo de configuración

En la ciencia de redes , el modelo de configuración es un método para generar redes aleatorias a partir de una secuencia de grados dada . Se utiliza ampliamente como modelo de referencia para redes sociales de la vida real , ya que permite al modelador incorporar distribuciones de grados arbitrarios.

En el modelo de configuración, el grado de cada vértice está predefinido, en lugar de tener una distribución de probabilidad de la cual se elige el grado dado. ^[2] A diferencia del modelo Erdős–Rényi , la secuencia de grados del modelo de configuración no está restringida a tener una distribución de Poisson , el modelo permite al usuario darle a la red cualquier distribución de grados deseada.

El siguiente algoritmo describe la generación del modelo:

1. Tomar una secuencia de grados, es decir, asignar un grado a cada vértice. Los grados de los vértices se representan como semienlaces o stubs. La suma de stubs debe ser par para poder construir un grafo ( ). La secuencia de grados se puede extraer de una distribución teórica o puede representar una red real (determinada a partir de la matriz de adyacencia de la red).${\displaystyle k_{i}}$${\displaystyle \sum k_{i}=2m}$
2. Elija dos stubs de manera uniforme y aleatoria y conéctelos para formar una arista. Elija otro par de los stubs restantes y conéctelos. Continúe hasta que se quede sin stubs. El resultado es una red con la secuencia de grados predefinida. La realización de la red cambia con el orden en que se eligen los stubs, pueden incluir ciclos (b), bucles propios (c) o enlaces múltiples (d) (Figura 1).${\displaystyle 2m-2}$

El algoritmo descrito anteriormente combina todos los stubs con la misma probabilidad. La distribución uniforme de la coincidencia es una propiedad importante en términos de calcular otras características de las redes generadas. El proceso de generación de la red no excluye el evento de generar un bucle propio o un enlace múltiple. Si diseñamos el proceso de manera que no se permitan los bucles propios ni los enlaces múltiples, la coincidencia de los stubs no seguiría una distribución uniforme.

El número total esperado de enlaces múltiples en una red de modelo de configuración sería:

${\displaystyle {\frac {1}{2}}{\Big [}{\frac {\langle {k^{2}}\rangle }{\langle k\rangle }}-1{\Big ]}^{2}}$

donde es el momento n-ésimo de la distribución de grados. Por lo tanto, el número promedio de bucles propios y enlaces múltiples es una constante para algunas redes grandes, y la densidad de bucles propios y enlaces múltiples, es decir, el número por nodo, tiende a cero siempre que sea constante y finito. Para algunas distribuciones de grados de ley de potencia donde el segundo momento diverge, la densidad de enlaces múltiples puede no desaparecer o puede hacerlo más lentamente que . ^[2]${\displaystyle \langle {k^{n}}\rangle }$${\displaystyle N\rightarrow \infty }$${\displaystyle \langle {k^{2}}\rangle }$${\displaystyle {N}^{-1}}$

Otra consecuencia de los bucles propios y las aristas múltiples es que no todas las redes posibles se generan con la misma probabilidad. En general, todas las realizaciones posibles se pueden generar permutando los stubs de todos los vértices de todas las formas posibles. El número de permutaciones de los stubs de un nodo es , por lo que el número de realizaciones de una secuencia de grados es . Esto significaría que cada realización ocurre con la misma probabilidad. Sin embargo, los bucles propios y las aristas múltiples pueden cambiar el número de realizaciones, ya que la permutación de aristas propias puede dar como resultado una realización sin cambios. Dado que el número de bucles propios y enlaces múltiples se desvanece cuando , la variación en las probabilidades de diferentes realizaciones será pequeña pero presente. ^[2]${\displaystyle i}$${\displaystyle k_{i}!}$${\displaystyle N\{k_{i}\}=\prod _{i}k_{i}!}$${\displaystyle N\rightarrow \infty }$

Un trozo de nodo puede estar conectado a otros trozos (hay trozos en total, y tenemos que excluir el que estamos observando actualmente). El vértice tiene trozos a los que se puede conectar el nodo con la misma probabilidad (debido a la distribución uniforme). La probabilidad de que un trozo de nodo esté conectado a uno de estos trozos es . Dado que el nodo tiene trozos, la probabilidad de estar conectado a es ( para α suficientemente grande ). Nótese que esta fórmula solo puede verse como una probabilidad si , y más precisamente describe el número esperado de aristas entre nodos y . Nótese que esta fórmula no se aplica al caso de autoaristas. ^[2]${\displaystyle i}$${\displaystyle 2m-1}$${\displaystyle 2m}$${\displaystyle j}$${\displaystyle k_{j}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle k_{j}}$${\displaystyle {\frac {k_{j}}{2m-1}}}$${\displaystyle i}$${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle {\frac {k_{i}k_{j}}{2m-1}}}$${\displaystyle {\frac {k_{i}k_{j}}{2m}}}$${\displaystyle m}$${\displaystyle k_{i}k_{j}/2m\ll 1}$${\displaystyle i}$${\displaystyle j}$

Dado un modelo de configuración con una distribución de grados , la probabilidad de que un nodo elegido al azar tenga grado es . Pero si tomamos uno de los vértices al que podemos llegar siguiendo una de las aristas de i, la probabilidad de que tenga grado k es . (La probabilidad de llegar a un nodo con grado k es , y existen tales nodos). Esta fracción depende de en lugar del grado del nodo típico con . Por lo tanto, se espera que un vecino de un nodo típico tenga un grado más alto que el propio nodo típico. Esta característica del modelo de configuración describe bien el fenómeno de "mis amigos tienen más amigos que yo". ${\displaystyle p_{k}}$${\displaystyle i}$${\displaystyle k}$${\displaystyle p_{k}}$${\displaystyle {\frac {k}{2m}}\times np_{k}={\frac {kp_{k}}{\left\langle k\right\rangle }}}$${\displaystyle {\frac {k}{2m}}}$${\displaystyle np_{k}}$${\displaystyle kp_{k}}$${\displaystyle p_{k}}$

El coeficiente de agrupamiento (la probabilidad promedio de que los vecinos de un nodo estén conectados) se calcula aproximadamente de la siguiente manera: ${\displaystyle C_{g}}$

${\displaystyle C_{g}=\sum _{k_{i},k_{j}=1}^{\infty }q_{k_{i}}q_{k_{j}}{\frac {(k_{i}-1)(k_{j}-1)}{2m}},}$

donde denota la probabilidad de que una arista aleatoria alcance un vértice de grado, y los factores de la forma " " en lugar de " " aparecen porque se ha tenido en cuenta un trozo por el hecho de que estos son vecinos de un vértice común. Al evaluar los resultados anteriores, ${\displaystyle q_{k}}$${\displaystyle k}$${\displaystyle k_{i}-1}$${\displaystyle k_{i}}$

${\displaystyle C_{g}={\frac {1}{2m}}\left[\sum _{k=0}^{\infty }(k-1)q_{k}\right]^{2}.}$

Usando y , con denotando la distribución de grados, denotando el grado promedio y denotando el número de vértices, lo anterior se convierte en ${\displaystyle q_{k}=kp_{k}/\langle k\rangle }$${\displaystyle 2m=N\langle k\rangle }$${\displaystyle p_{k}}$${\displaystyle \langle k\rangle }$${\displaystyle N}$

${\displaystyle C_{g}={\frac {1}{N\langle k\rangle ^{3}}}\left[\sum _{k=1}^{\infty }(k-1)kP(k)\right]^{2}={\frac {\left(\langle k^{2}\rangle -\langle k\rangle \right)^{2}}{N\langle k\rangle ^{3}}},}$

con denotación del segundo momento de la distribución de grados. Suponiendo que y son constantes, lo anterior se comporta como ${\displaystyle \langle k^{2}\rangle }$${\displaystyle \langle k^{2}\rangle }$${\displaystyle \langle k\rangle }$

${\displaystyle C_{g}\sim {\frac {\mathrm {const} }{N}},}$

donde la constante depende de . ^[2] Por lo tanto, el coeficiente de agrupamiento se vuelve pequeño en el límite. ${\displaystyle p_{k}}$${\displaystyle C_{g}}$${\displaystyle N\gg 1}$

En el modelo de configuración, existe un componente gigante (GC) si

${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0,}$

donde y son el primer y segundo momento de la distribución de grados . Esto significa que el umbral crítico depende únicamente de cantidades que están determinadas de forma única por la distribución de grados . ${\displaystyle \langle k\rangle }$${\displaystyle \langle k^{2}\rangle }$${\displaystyle p_{k}}$

El modelo de configuración genera redes locales tipo árbol, lo que significa que cualquier vecindario local en dicha red toma la forma de un árbol. Más precisamente, si se comienza en cualquier nodo de la red y se forma el conjunto de todos los nodos a una distancia o menos de ese nodo de inicio, el conjunto, con una probabilidad que tiende a 1 cuando n → ∞, tomará la forma de un árbol. ^[3] En estructuras tipo árbol, el número de segundos vecinos promediado en toda la red, , es:${\displaystyle d}$${\displaystyle c_{2}}$${\displaystyle c_{2}=\langle k^{2}\rangle -\langle k\rangle .}$

Entonces, en general, el número promedio a distancia se puede escribir como: ${\displaystyle d}$

${\displaystyle c_{d}=\left({\frac {c_{2}}{c_{1}}}\right)^{d-1}c_{1}.}$

Lo que implica que si la razón de es mayor que uno, entonces la red puede tener un componente gigante. Esto es conocido como el criterio de Molloy-Reed. ^[4] La intuición detrás de este criterio es que si existe el componente gigante (GC), entonces el grado promedio de un vértice elegido aleatoriamente en un componente conectado debe ser al menos 2. El criterio de Molloy-Reed también puede expresarse como: lo que implica que, aunque el tamaño del GC puede depender de y , el número de nodos de grado 0 y 2 no tiene ninguna contribución en la existencia del componente gigante. ^[3]${\displaystyle {\frac {c_{2}}{c_{1}}}}$${\displaystyle i}$${\displaystyle \sum _{i}k_{i}(k_{i}-2)>0,}$${\displaystyle p_{0}}$${\displaystyle p_{2}}$

El modelo de configuración puede asumir cualquier distribución de grados y muestra el efecto de mundo pequeño , ya que para el orden principal el diámetro del modelo de configuración es solo . ^[5]${\displaystyle d={\frac {\ln(N)}{\ln(c_{2}/c_{1})}}}$

Como el número total de vértices tiende a infinito, la probabilidad de encontrar dos componentes gigantes se desvanece. Esto significa que en el régimen disperso, el modelo consta de un componente gigante (si lo hay) y múltiples componentes conectados de tamaño finito. Los tamaños de los componentes conectados se caracterizan por su distribución de tamaño : la probabilidad de que un vértice muestreado aleatoriamente pertenezca a un componente conectado de tamaño. Existe una correspondencia entre la distribución de grados y la distribución de tamaño. Cuando el número total de vértices tiende a infinito, , se produce la siguiente relación: ^[6]${\displaystyle N}$${\displaystyle w_{n}}$${\displaystyle n.}$${\displaystyle p_{k}}$${\displaystyle w_{n}.}$${\displaystyle N\rightarrow \infty }$

${\displaystyle w_{n}={\begin{cases}{\frac {\langle k\rangle }{n-1}}u_{1}^{*n}(n-2),&n>1,\\p_{0}&n=1,\end{cases}}}$

donde y denota la potencia de convolución de pliegues . Además, se conocen asíntotas explícitas para cuando y es cercano a cero. ^[6] Las expresiones analíticas para estas asíntotas dependen de la finitud de los momentos del exponente de cola de la distribución de grados (cuando presenta una cola pesada) y del signo del criterio de Molloy-Reed. La siguiente tabla resume estas relaciones (las constantes se proporcionan en ^[6] ). ${\displaystyle u_{1}(k):={\frac {k+1}{\langle k\rangle }}p_{k+1},}$${\displaystyle u_{1}^{*n}}$${\displaystyle n}$${\displaystyle w_{n}}$${\displaystyle n\gg 1}$${\displaystyle |\langle k^{2}\rangle -2\langle k\rangle |}$${\displaystyle p_{k},}$${\displaystyle \beta }$${\displaystyle p_{k}}$

Tres propiedades generales de las redes complejas son la distribución de grado heterogénea, la longitud de camino promedio corta y el alto agrupamiento. ^{[1] [7] [8]} Al tener la oportunidad de definir cualquier secuencia de grado arbitraria, la primera condición se puede satisfacer por diseño, pero como se muestra arriba, el coeficiente de agrupamiento global es una función inversa del tamaño de la red, por lo que para redes de configuración grandes, el agrupamiento tiende a ser pequeño. Esta característica del modelo de referencia contradice las propiedades conocidas de las redes empíricas, pero las extensiones del modelo pueden resolver este problema (ver ^[9] ). Todas las redes generadas por este modelo son localmente similares a árboles siempre que el promedio de la distribución de grado en exceso sea constante o crezca más lentamente que la raíz cuadrada del número de enlaces, . En otras palabras, este modelo evita la formación de subestructuras como bucles en el límite de tamaño grande. La desaparición del coeficiente de agrupamiento, es un caso especial de este resultado más general. Si bien la propiedad similar a un árbol hace que el modelo no sea muy realista, muchos cálculos, como los métodos de función generadora , son posibles para el modelo de configuración gracias a esta característica. ^[3]${\displaystyle {\sqrt {m}}}$

El modelo de configuración se aplica como parámetro de referencia en el cálculo de la modularidad de la red . La modularidad mide el grado de división de la red en módulos. Se calcula de la siguiente manera:

${\displaystyle Q={\frac {1}{2L}}\sum _{i\neq j}{\Bigl (}A_{ij}-{\frac {k_{i}k_{j}}{2L}}{\Bigr )}\delta (C_{i},C_{j})}$^[10]

en el que se compara la matriz de adyacencia de la red con la probabilidad de tener una arista entre el nodo y (dependiendo de sus grados) en el modelo de configuración (ver la página modularidad para más detalles). ${\displaystyle i}$${\displaystyle j}$

En el DCM (modelo de configuración dirigida), ^[11] a cada nodo se le asigna una cantidad de semiaristas llamadas colas y caras. Luego, las colas y las caras se emparejan de manera uniforme y aleatoria para formar aristas dirigidas. El tamaño del componente gigante, ^{[11] [12]} la distancia típica ^[13] y el diámetro ^[14] del DCM se han estudiado matemáticamente. También se han realizado investigaciones exhaustivas sobre los recorridos aleatorios en el DCM. ^{[15] [16] [17]} Algunas redes complejas del mundo real han sido modeladas por el DCM, como las redes neuronales ^[18] , las redes financieras ^{[19] y las redes sociales [20]} .