En ciencia de redes , el modelo de configuración es un método para generar redes aleatorias a partir de una secuencia de grados determinada . Es muy utilizado como modelo de referencia para las redes sociales de la vida real , porque permite al usuario incorporar distribuciones de grados arbitrarias.
Justificación del modelo
En el modelo de configuración, el grado de cada vértice está predefinido, en lugar de tener una distribución de probabilidad a partir 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 para tener una distribución de Poisson , el modelo permite al usuario dar a la red cualquier distribución de grados deseada.
Algoritmo
El siguiente algoritmo describe la generación del modelo:
- Tome una secuencia de grados, es decir, asigne un título a cada vértice. Los grados de los vértices se representan como medios enlaces o stubs. La suma de stubs debe ser par para poder construir un gráfico (). La secuencia de grados puede extraerse de una distribución teórica o puede representar una red real (determinada a partir de la matriz de adyacencia de la red).
- Elija dos talones uniformemente al azar y conéctelos para formar un borde. Elija otro par de los restantesstubs y conectarlos. Continúe hasta que se le acaben los talones. El resultado es una red con la secuencia de grados predefinida. La realización de la red cambia con el orden en el que se eligen los stubs, pueden incluir ciclos (b), auto-bucles (c) o multienlace (d) (Figura 1) Sin embargo, el número esperado de auto-bucles y los enlaces múltiples llegan a cero en el límite N → ∞. [1]
Auto-bucles, múltiples aristas e implicaciones
El algoritmo descrito anteriormente coincide con cualquier código auxiliar con la misma probabilidad. La distribución uniforme del emparejamiento es una propiedad importante en términos de cálculo de otras características de las redes generadas. El proceso de generación de la red no excluye el evento de generar un self-loop o un multi-link. Si diseñáramos el proceso en el que no se permiten bucles automáticos y bordes múltiples, la coincidencia de los stubs no seguiría una distribución uniforme. Sin embargo, el número promedio de bucles propios y múltiples bordes es una constante para redes grandes, por lo que la densidad de bucles propios y enlaces múltiples llega a cero a medida que[2] (ver el libro citado para más detalles).
Una consecuencia adicional de los bucles automáticos y los bordes 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 permutación de los stubs del 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 automáticos y los bordes múltiples pueden cambiar el número de realizaciones, ya que la permutación de los bordes propios puede dar como resultado una realización sin cambios. Dado que el número de auto-bucles y enlaces múltiples desaparece a medida que, la variación en las probabilidades de realización diferente será pequeña pero presente. [2]
Propiedades
Probabilidad de borde
Un trozo de nodo se puede conectar a otros talones (hay stubs por completo, y tenemos que excluir el que estamos observando actualmente). El vértice posee stubs a qué nodo se puede conectar con la misma probabilidad (debido a la distribución uniforme). La probabilidad de un trozo de nodo estar conectado a uno de estos stubs es . Desde nodo posee talones, la probabilidad de estar conectado a es ( para suficientemente grande ). Tenga en cuenta que esta fórmula solo puede verse como una probabilidad si, y más precisamente describe el número esperado de bordes entre nodos y . Tenga en cuenta que esta fórmula no se aplica al caso de los bordes propios. [2]
Dado un modelo de configuración con una distribución de grados , la probabilidad de un nodo elegido al azar tener grado es . Pero si tomamos uno de los vértices a los que podemos llegar siguiendo una de las aristas de i, la probabilidad de tener grado k es. (La probabilidad de alcanzar un nodo con grado k es, y aquí están tales nodos.) Esta fracción depende de a diferencia 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".
Coeficiente de agrupamiento
El coeficiente de agrupamiento (la probabilidad promedio de que los vecinos de un nodo estén conectados) se calcula aproximadamente de la siguiente manera:
,
dónde denota la probabilidad de que un borde aleatorio alcance un grado- vértice y los factores de la forma "" en vez de ""aparecen porque un talón se ha tenido en cuenta por el hecho de que son vecinos de un vértice común. La evaluación de los resultados anteriores en
Utilizando y , con que denota la distribución de grados, que denota el grado medio, y denotando el número de vértices, lo anterior se convierte en
con que denota el segundo momento de la distribución de grados. Asumiendo que y son constantes, lo anterior se comporta como
donde la constante depende de . [2] Por lo tanto, el coeficiente de agrupamiento se vuelve pequeño en el límite.
Componente gigante
En el modelo de configuración, existe un componente gigante (GC) si
dónde y son el primer y segundo momento de la distribución de grados . Eso significa que, el umbral crítico depende únicamente de las cantidades que están determinadas únicamente por la distribución de grados.
El modelo de configuración genera redes locales en forma de árbol, lo que significa que cualquier vecindario local en dicha red toma la forma de un árbol. Más precisamente, si comienza en cualquier nodo de la red y forma el conjunto de todos los nodos a distanciao menos desde ese nodo inicial, el conjunto, con probabilidad tendiendo a 1 cuando n → ∞, tomará la forma de un árbol. [3] En estructuras en forma de árbol, el número de segundos vecinos promediado en toda la red,, es:
Entonces, en general, el número promedio a distancia Se puede escribir como:
Lo que implica que si la razón de es mayor que uno, entonces la red puede tener un componente gigante. Esto es famoso como el criterio de Molloy-Reed. [4] La intuición detrás de este criterio es que si el componente gigante existe, entonces el grado promedio de un vértice elegido al azar en un componente conectado debe ser al menos 2. El criterio de Molloy-Reed también se puede expresar 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 contribución en la existencia del componente gigante. [3]
Diámetro
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]
Componentes de tamaño finito
Como número total de vértices tiende al infinito, la probabilidad de encontrar dos componentes gigantes se está desvaneciendo. 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ños.- la probabilidad de que un vértice muestreado aleatoriamente pertenezca a un componente de tamaño conectado Existe una correspondencia entre la distribución de títulos y la distribución del tamaño Cuando el número total de vértices tiende a infinito, , se produce la siguiente relación: [6]
dónde y denota el -Potencia de convolución . Además, asíntotas explícitas para son conocidos cuando y está cerca de cero. [6] Las expresiones analíticas para estas asíntotas dependen de la finitud de los momentos de el exponente de cola de distribución de grados (Cuándo presenta una cola pesada), y el signo de Criterium de Molloy-Reed. La siguiente tabla resume estas relaciones (las constantes se proporcionan en [6] ).
Momentos de | Cola de | ||
---|---|---|---|
cola ligera | -1 o 1 | ||
0 | |||
cola pesada, | -1 | ||
0 | |||
1 | |||
| cola pesada, | -1 | |
0 | |||
1 | |||
cola pesada, | -1 | ||
0 | |||
1 | |||
| cola pesada, | 1 | |
cola pesada, | 1 |
Modelado
Comparación con las redes del mundo real
Tres propiedades generales de las redes complejas son la distribución de grados heterogénea, la longitud de ruta media corta y la alta agrupación. [1] [7] [8] Teniendo la oportunidad de definir cualquier secuencia de grados 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 configuraciones grandes redes, la agrupación tiende a ser pequeña. Esta característica del modelo de línea de base contradice las propiedades conocidas de las redes empíricas, pero las extensiones del modelo pueden resolver este problema (ver [9] ).
Aplicación: cálculo de modularidad
El modelo de configuración se aplica como 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:
en el que la matriz de adyacencia de la red se compara con la probabilidad de tener un borde entre el nodo y (dependiendo de sus grados) en el modelo de configuración (ver modularidad en la página para más detalles).
Modelo de configuración dirigida
En el DCM (modelo de configuración dirigida), [11] a cada nodo se le asigna un número de medios bordes llamados colas y cabezas. Luego, las colas y las cabezas se emparejan uniformemente al azar para formar bordes dirigidos. El tamaño del componente gigante, [11] [12] la distancia típica, [13] y el diámetro [14] de DCM se han estudiado matemáticamente. También ha habido una extensa investigación sobre paseos aleatorios en DCM. [15] [16] [17] Algunas redes complejas del mundo real han sido modeladas por DCM, como redes neuronales, [18] finanzas [19] y redes sociales. [20]
Referencias
- ^ a b c Ciencia en red por Albert-László Barabási .
- ^ a b c d e Newman, Mark (25 de marzo de 2010). Redes: una introducción - Beca de Oxford . Prensa de la Universidad de Oxford. doi : 10.1093 / acprof: oso / 9780199206650.001.0001 . ISBN 9780191594175.
- ^ a b Newman, Mark (18 de octubre de 2018). Redes . 1 . Prensa de la Universidad de Oxford. doi : 10.1093 / oso / 9780198805090.001.0001 . ISBN 978-0-19-880509-0.
- ^ Molloy, Michael; Reed, Bruce (1 de marzo de 1995). "Un punto crítico para los gráficos aleatorios con una determinada secuencia de grados". Estructuras y algoritmos aleatorios . 6 (2-3): 161-180. CiteSeerX 10.1.1.24.6195 . doi : 10.1002 / rsa.3240060204 . ISSN 1098-2418 .
- ^ Chung, Fan; Lu, Linyuan (10 de diciembre de 2002). "Las distancias medias en gráficos aleatorios con grados esperados dados" . Actas de la Academia Nacional de Ciencias . 99 (25): 15879-15882. Código Bibliográfico : 2002PNAS ... 9915879C . doi : 10.1073 / pnas.252631999 . ISSN 0027-8424 . PMC 138532 . PMID 12466502 .
- ^ a b c Kryven, yo (2017). "Expresión general para la distribución del tamaño de los componentes en redes de configuración infinita" . Revisión E física . 95 (5): 052303. arXiv : 1703.05413 . Código bibliográfico : 2017PhRvE..95e2303K . doi : 10.1103 / PhysRevE.95.052303 . hdl : 11245.1 / fa1b270b-61a5-4f20-b496-ddf446fdfe80 . PMID 28618550 . S2CID 8421307 .
- ^ Barabási, Albert-László; Albert, Réka (15 de octubre de 1999). "Aparición del escalado en redes aleatorias". Ciencia . 286 (5439): 509–512. arXiv : cond-mat / 9910332 . Código Bibliográfico : 1999Sci ... 286..509B . doi : 10.1126 / science.286.5439.509 . ISSN 0036-8075 . PMID 10521342 . S2CID 524106 .
- ^ Watts, Duncan J .; Strogatz, Steven H. (1998). "Dinámica colectiva de las redes de 'pequeños mundos'". Naturaleza . 393 (6684): 440–442. Código Bibliográfico : 1998Natur.393..440W . doi : 10.1038 / 30918 . ISSN 1476-4687 . PMID 9623998 . S2CID 4429113 .
- ^ Newman, MEJ (2009). "Gráficos aleatorios con agrupación". Cartas de revisión física . 103 (5): 058701. arXiv : 0903.4009 . Código Bibliográfico : 2009PhRvL.103e8701N . doi : 10.1103 / physrevlett.103.058701 . PMID 19792540 . S2CID 28214709 .
- ^ Newman, MEJ (2004). "Encontrar y evaluar la estructura comunitaria en redes". Revisión E física . 69 (2): 026113. arXiv : cond-mat / 0308217 . Código Bibliográfico : 2004PhRvE..69b6113N . doi : 10.1103 / physreve.69.026113 . PMID 14995526 . S2CID 197314 .
- ^ a b COOPER, COLIN; FRIEZE, ALAN (mayo de 2004). "El tamaño del componente más grande fuertemente conectado de un dígrafo aleatorio con una secuencia de grados dada" . Combinatoria, Probabilidad y Computación . 13 (3): 319–337. doi : 10.1017 / S096354830400611X . ISSN 1469-2163 .
- ^ Cai, Xing Shi; Perarnau, Guillem (10 de abril de 2020). "El componente gigante del modelo de configuración dirigida revisitado". arXiv : 2004.04998 [ math.PR ].
- ^ van der Hoorn, Pim; Olvera-Cravioto, Mariana (junio de 2018). "Distancias típicas en el modelo de configuración dirigida". Los anales de la probabilidad aplicada . 28 (3): 1739-1792. arXiv : 1511.04553 . doi : 10.1214 / 17-AAP1342 . S2CID 13683470 .
- ^ Cai, Xing Shi; Perarnau, Guillem (10 de marzo de 2020). "El diámetro del modelo de configuración dirigida". arXiv : 2003.04965 [ math.PR ].
- ^ Bordenave, Charles; Caputo, Pietro; Salez, Justin (1 de abril de 2018). "Caminata aleatoria en dígrafos aleatorios escasos" . Teoría de la probabilidad y campos relacionados . 170 (3): 933–960. arXiv : 1508.06600 . doi : 10.1007 / s00440-017-0796-7 . ISSN 1432-2064 . S2CID 55211047 .
- ^ Caputo, Pietro; Quattropani, Matteo (1 de diciembre de 2020). "Distribución estacionaria y tiempo de cobertura de modelos de configuración dirigida dispersa" . Teoría de la probabilidad y campos relacionados . 178 (3): 1011–1066. doi : 10.1007 / s00440-020-00995-6 . ISSN 1432-2064 . S2CID 202565916 .
- ^ Cai, Xing Shi; Perarnau, Guillem (14 de octubre de 2020). "Valores estacionarios mínimos de gráficos dispersos dirigidos al azar". arXiv : 2010.07246 [ math.PR ].
- ^ Amini, Hamed (1 de noviembre de 2010). "Bootstrap Percolation en Living Neural Networks". Revista de física estadística . 141 (3): 459–475. arXiv : 0910.0627 . Código bibliográfico : 2010JSP ... 141..459A . doi : 10.1007 / s10955-010-0056-z . ISSN 1572-9613 . S2CID 7601022 .
- ^ Amini, Hamed; Minca, Andreea (2013). "Modelización matemática de riesgo sistémico". Avances en el análisis de redes y sus aplicaciones . Matemáticas en la industria. Saltador. 18 : 3-26. doi : 10.1007 / 978-3-642-30904-5_1 . ISBN 978-3-642-30903-8. S2CID 166867930 .
- ^ Li, Hui (julio de 2018). "Ataque a la vulnerabilidad de las redes sociales online". 2018 37th Chinese Control Conference (CCC) : 1051–1056. doi : 10.23919 / ChiCC.2018.8482277 . ISBN 978-988-15639-5-8. S2CID 52933445 .