Modelo Barabási-Albert

Algoritmo de generación de red sin escala

Visualización de tres gráficos generados con el modelo Barabasi-Albert (BA). Cada uno tiene 20 nodos y un parámetro de adjunto m como se especifica. El color de cada nodo depende de su grado (misma escala para cada gráfico).

El modelo Barabási-Albert (BA) es un algoritmo para generar redes aleatorias sin escala utilizando un mecanismo de conexión preferencial . Se cree que varios sistemas naturales y creados por el hombre, incluidos Internet , la World Wide Web , las redes de citas y algunas redes sociales , tienen una escala aproximadamente libre y ciertamente contienen pocos nodos (llamados centros) con un grado inusualmente alto en comparación con los demás. nodos de la red. El modelo BA intenta explicar la existencia de este tipo de nodos en redes reales. El algoritmo lleva el nombre de sus inventores Albert-László Barabási y Réka Albert .

Conceptos

Muchas redes observadas (al menos aproximadamente) entran en la clase de redes sin escala , lo que significa que tienen distribuciones de grados de ley de potencia (o sin escala), mientras que los modelos de gráficos aleatorios como el modelo Erdős-Rényi (ER) y el El modelo Watts-Strogatz (WS) no exhibe leyes de potencia. El modelo Barabási-Albert es uno de varios modelos propuestos que generan redes sin escala. Incorpora dos conceptos generales importantes: crecimiento y apego preferencial . Tanto el crecimiento como el apego preferencial existen ampliamente en las redes reales.

El crecimiento significa que la cantidad de nodos en la red aumenta con el tiempo.

El vínculo preferencial significa que cuanto más conectado esté un nodo, más probabilidades tendrá de recibir nuevos enlaces. Los nodos con un grado más alto tienen una mayor capacidad para capturar enlaces agregados a la red. Intuitivamente, el vínculo preferencial puede entenderse si pensamos en términos de redes sociales que conectan a las personas. Aquí, un vínculo de A a B significa que la persona A "conoce" o "está familiarizada con" la persona B. Los nodos fuertemente vinculados representan personas conocidas con muchas relaciones. Cuando un recién llegado ingresa a la comunidad, es más probable que conozca a una de esas personas más visibles que a un relativamente desconocido. El modelo BA se propuso suponiendo que en la World Wide Web las nuevas páginas enlazan preferentemente con hubs, es decir, sitios muy conocidos como Google , en lugar de páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularla eligiendo aleatoriamente un enlace existente, la probabilidad de seleccionar una página en particular sería proporcional a su grado. El modelo BA afirma que esto explica la regla de probabilidad de vinculación preferencial.

Posteriormente, el modelo Bianconi-Barabási trabaja para abordar este problema introduciendo un parámetro de "aptitud". El vínculo preferencial es un ejemplo de un ciclo de retroalimentación positiva en el que las variaciones inicialmente aleatorias (un nodo que inicialmente tiene más enlaces o ha comenzado a acumular enlaces antes que otro) se refuerzan automáticamente, magnificando así enormemente las diferencias. A esto también se le llama a veces efecto Matthew , "los ricos se hacen más ricos ". Véase también autocatálisis .

Algoritmo

Los pasos del crecimiento de la red según el modelo Barabasi-Albert ( ) ${\displaystyle m_{0}=m=2}$

El único parámetro en el modelo BA es , un número entero positivo. La red se inicializa con una red de nodos. ${\displaystyle m}$ ${\displaystyle m_{0}\geq m}$

En cada paso, agregue un nuevo nodo, luego muestree los vértices existentes de la red, con una probabilidad proporcional al número de enlaces que los nodos existentes ya tienen (los documentos originales no especificaban cómo manejar los casos en los que el mismo nodo existente se elige varias veces). Formalmente, la probabilidad de que el nuevo nodo esté conectado al nodo es ^[1] ${\displaystyle m}$ ${\displaystyle p_{i}}$ ${\displaystyle i}$

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

donde es el grado del nodo y la suma se realiza sobre todos los nodos preexistentes (es decir, el denominador da como resultado el doble del número actual de aristas en la red). Este paso se puede realizar muestreando primero de manera uniforme un borde y luego muestreando uno de los dos vértices del borde. ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle j}$

Los nodos muy vinculados ("hubs") tienden a acumular rápidamente aún más vínculos, mientras que los nodos con sólo unos pocos vínculos probablemente no sean elegidos como destino para un nuevo vínculo. Los nuevos nodos tienen una "preferencia" de unirse a los nodos que ya están fuertemente vinculados.

Una red de árboles generada según el modelo de Barabasi-Albert. La red está formada por 50 vértices con grados iniciales . ${\displaystyle m_{0}=1}$

Propiedades

Distribución de grados

La distribución de los grados de vértice de un gráfico BA con 200000 nodos y 2 nuevas aristas por paso. Trazado en escala logarítmica. Sigue una ley de potencia con exponente -2,78.

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

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

Distribución del índice de Hirsch

Se demostró que la distribución del índice h o índice de Hirsch también estaba libre de escala y se propuso como índice de lobby, para ser utilizado como medida de centralidad ^[2]

${\displaystyle H(k)\sim k^{-6}\,}$

Además, se puede obtener un resultado analítico para la densidad de nodos con índice h 1 en el caso de que ${\displaystyle m_{0}=1}$

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

Correlaciones de grado de nodo

Las correlaciones entre los grados de nodos conectados se desarrollan espontáneamente en el modelo BA debido a la forma en que evoluciona la red. La probabilidad, de encontrar un vínculo que conecte un nodo de grado con un nodo ancestro de grado en el modelo BA para el caso especial de (árbol BA) está dada por ${\displaystyle n_{k\ell }}$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle m=1}$

${\displaystyle n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.}$

Esto confirma la existencia de correlaciones de grado, porque si las distribuciones no estuvieran correlacionadas, obtendríamos . ^[1] ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$

En general , la fracción de enlaces que conectan un nodo de grado con un nodo de grado es ^[3] ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle \ell }$

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

Además, la distribución de grados del vecino más cercano , es decir, la distribución de grados de los vecinos de un nodo con grado , viene dada por ^[3] ${\displaystyle p(\ell \mid k)}$ ${\displaystyle k}$

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

En otras palabras, si seleccionamos un nodo con grado y luego seleccionamos uno de sus vecinos al azar, la probabilidad de que este vecino seleccionado al azar tenga grado viene dada por la expresión anterior. ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle p(\ell |k)}$

Coeficiente de agrupamiento

^{Klemm y Eguíluz [4]} obtuvieron un resultado analítico para el coeficiente de agrupamiento del modelo BA y lo demostró Bollobás. ^[5] Fronczak, Fronczak y Holyst aplicaron un enfoque de campo medio para estudiar el coeficiente de agrupamiento. ^[6]

Este comportamiento aún es distinto del comportamiento de las redes de mundos pequeños donde la agrupación es independiente del tamaño del sistema. En el caso de redes jerárquicas, la agrupación en función del grado de nodo también sigue una ley de potencia,

${\displaystyle C(k)=k^{-1}.\,}$

Este resultado fue obtenido analíticamente por Dorogovtsev, Goltsev y Mendes. ^[7]

Propiedades espectrales

La densidad espectral del modelo BA tiene una forma diferente a la densidad espectral semicircular del gráfico aleatorio. Tiene forma de triángulo con la parte superior muy por encima del semicírculo y los bordes decayendo como una ley de potencia. ^[8] En ^[9] (Sección 5.1), se demostró que la forma de esta densidad espectral no es una función triangular exacta analizando los momentos de la densidad espectral en función del exponente de la ley potencial.

Escalado dinámico

Distribución de grados generalizada del modelo BA para . ${\displaystyle F(q,t)}$ ${\displaystyle m=1}$

Los mismos datos se trazan en coordenadas autosemejantes y brindan una excelente revelación colapsada que exhibe una escala dinámica. ${\displaystyle t^{1/2}F(q,N)}$ ${\displaystyle q/t^{1/2}}$ ${\displaystyle F(q,t)}$

Por definición, el modelo BA describe un fenómeno que se desarrolla en el tiempo y, por lo tanto, además de su propiedad libre de escala, también se podría buscar su propiedad de escala dinámica. En la red BA, los nodos también se pueden caracterizar por el grado generalizado , el producto de la raíz cuadrada del tiempo de nacimiento de cada nodo y su grado correspondiente , en lugar del grado solo, ya que el tiempo de nacimiento importa en la red BA. Encontramos que la distribución de grados generalizada tiene algunas características no triviales y exhibe una escala dinámica. ${\displaystyle q}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle F(q,t)}$

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

Implica que las distintas gráficas de vs colapsarían en una curva universal si trazamos vs. ^[10] ${\displaystyle F(q,t)}$ ${\displaystyle q}$ ${\displaystyle F(q,t)t^{1/2}}$ ${\displaystyle q/t^{1/2}}$

Casos limitantes

Modelo A

El modelo A conserva el crecimiento pero no incluye el apego preferencial. La probabilidad de que un nuevo nodo se conecte a cualquier nodo preexistente es igual. La distribución de grados resultante en este límite es geométrica, ^[11] lo que indica que el crecimiento por sí solo no es suficiente para producir una estructura sin escala.

Modelo B

El modelo B conserva el apego preferencial pero elimina el crecimiento. El modelo comienza con un número fijo de nodos desconectados y agrega enlaces, eligiendo preferentemente nodos de alto grado como destinos de enlace. Aunque la distribución de grados al principio de la simulación parece libre de escala, la distribución no es estable y eventualmente se vuelve casi gaussiana a medida que la red se acerca a la saturación. De modo que el apego preferencial por sí solo no es suficiente para producir una estructura libre de escala.

El hecho de que los modelos A y B no conduzcan a una distribución sin escala indica que se necesitan crecimiento y conexión preferencial simultáneamente para reproducir la distribución estacionaria de la ley de potencias observada en redes reales. ^[1]

Adjunto preferencial no lineal

El modelo BA puede considerarse como un caso específico del modelo más general de vinculación preferencial no lineal (NLPA). ^[12] El algoritmo NLPA es idéntico al modelo BA con la probabilidad de vinculación reemplazada por la forma más general.

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

donde es un exponente positivo constante. 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 extendida . 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 libre de escala de la red se rompe en el límite del tamaño infinito del sistema. Sin embargo, si es sólo ligeramente mayor que , NLPA puede dar como resultado distribuciones de grados que parecen estar transitoriamente libres de escala. ^[13] ${\displaystyle \alpha }$ ${\displaystyle \alpha =1}$ ${\displaystyle 0<\alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha <1}$ ${\displaystyle \alpha >1}$ ${\displaystyle \alpha }$ ${\displaystyle 1}$

Historia

El apego preferencial hizo su primera aparición en 1923 en el célebre modelo de urna del matemático húngaro György Pólya en 1923. ^[14] El método de la ecuación maestra, que produce una derivación más transparente, fue aplicado al problema por Herbert A. Simon en 1955 ^{[ 15]} en el curso de estudios sobre el tamaño de las ciudades y otros fenómenos. Derek de Solla Price lo aplicó por primera vez para explicar las frecuencias de citas en 1976. ^[16] Price estaba interesado en la acumulación de citas de artículos científicos y el modelo de Price utilizaba la "ventaja acumulativa" (su nombre para el vínculo preferencial) para generar una gran distribución de cola. En el lenguaje de las redes de citas modernas, el modelo de Price produce una red dirigida, es decir, la versión del modelo de Barabási-Albert. El nombre "apego preferencial" y la actual popularidad de los modelos de red sin escala se debe al trabajo de Albert-László Barabási y Réka Albert , quienes descubrieron que un proceso similar está presente en redes reales y aplicaron en 1999 el apego preferencial para explicar las distribuciones de grados observadas numéricamente en la web. ^[17]

Ver también

• Modelo Bianconi-Barabási
• proceso de restaurante chino
• Redes complejas
• Modelo Erdős-Rényi (ER)
• modelo de precio
• Teoría de la percolación
• Red sin escala
• Red del mundo pequeño
• Modelo de Watts y Strogatz

Referencias

1. Albert, Réka ; Barabási, Albert-László (2002). «Mecánica estadística de redes complejas» (PDF) . Reseñas de Física Moderna . 74 (47): 47–97. arXiv : cond-mat/0106096 . Código Bib : 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.
2. Korn, A .; Schubert, A.; Telcs, A. (2009). "Índice de lobby en redes". Física A. 388 (11): 2221–2226. arXiv : 0809.0514 . Código Bib : 2009PhyA..388.2221K. doi :10.1016/j.physa.2009.02.013. S2CID  1119190.
3. Fotouhi, Babak; Rabbat, Michael (2013). "Correlación de grados en gráficos sin escala". La revista física europea B. 86 (12): 510. arXiv : 1308.5169 . Código Bib : 2013EPJB...86..510F. doi :10.1140/epjb/e2013-40920-6. S2CID  7520124.
4. Klemm, K.; Eguíluz, VC (2002). "Crecientes redes sin escala con comportamiento de mundo pequeño". Revisión física E. 65 (5): 057102. arXiv : cond-mat/0107607 . Código bibliográfico : 2002PhRvE..65e7102K. doi : 10.1103/PhysRevE.65.057102. hdl :10261/15314. PMID  12059755. S2CID  12945422.
5. Bollobás, B. (2003). "Resultados matemáticos en gráficos aleatorios sin escala". Manual de gráficos y redes . págs. 1–37. CiteSeerX 10.1.1.176.6988 . 
6. Alberto, Reka; Barabasi, Albert-Laszlo; Hołyst, Janusz A (2003). "Teoría del campo medio para coeficientes de agrupamiento en redes de Barabasi-Albert". Física. Rev. E. 68 (4): 046126. arXiv : cond-mat/0306255 . Código bibliográfico : 2003PhRvE..68d6126F. doi : 10.1103/PhysRevE.68.046126. PMID  14683021. S2CID  2372695.
7. Dorogovtsev, SN; Goltsev, AV; Mendes, JFF (25 de junio de 2002). "Web sin escala pseudofractal". Revisión física E. 65 (6): 066122. arXiv : cond-mat/0112143 . Código bibliográfico : 2002PhRvE..65f6122D. doi : 10.1103/PhysRevE.65.066122. PMID  12188798. S2CID  13996254.
8. Farkas, IJ; Derényi, I.; Barabási, A.-L.; Vicsek, T. (20 de julio de 2001) [19 de febrero de 2001]. "Espectros de gráficos del" mundo real ": más allá de la ley del semicírculo". Revisión física E. 64 (2): 026704. arXiv : cond-mat/0102335 . Código bibliográfico : 2001PhRvE..64b6704F. doi : 10.1103/PhysRevE.64.026704. hdl :2047/d20000692. PMID  11497741. S2CID  1434432.
9. Preciado, VM; Rahimian, A. (diciembre de 2017). "Análisis espectral basado en momentos de gráficos aleatorios con una secuencia de grados esperada dada". Transacciones IEEE sobre ciencia e ingeniería de redes . 4 (4): 215–228. arXiv : 1512.03489 . doi : 10.1109/TNSE.2017.2712064 . S2CID  12187100.
10. MK Hassan, MZ Hassan y NI Pavel, “Escalado dinámico, colapso de datos y autosimilitud en redes Barabasi-Albert” J. Phys. R: Matemáticas. Teor. 44 175101 (2011) https://dx.doi.org/10.1088/1751-8113/44/17/175101
11. Pekoz, Erol; Rollin, A.; Ross, N. (2012). "Variación total y límites de error límite local para aproximación geométrica". Bernoulli . Archivado desde el original el 23 de septiembre de 2015 . Consultado el 25 de octubre de 2012 .
12. Krapivsky, PL; Redner, S.; Leyvraz, F. (20 de noviembre de 2000). "Conectividad de redes aleatorias en crecimiento". Cartas de revisión física . 85 (21): 4629–4632. arXiv : cond-mat/0005139 . Código Bib : 2000PhRvL..85.4629K. doi : 10.1103/PhysRevLett.85.4629. PMID  11082613. S2CID  16251662.
13. Krapivsky, Paul; Krioukov, Dmitri (21 de agosto de 2008). "Redes sin escala como regímenes preasintóticos de apego preferencial superlineal". Revisión física E. 78 (2): 026114. arXiv : 0804.1366 . Código bibliográfico : 2008PhRvE..78b6114K. doi : 10.1103/PhysRevE.78.026114. PMID  18850904. S2CID  14292535.
14. Albert-László, Barabási (2012). "Suerte o razón". Naturaleza . 489 (7417): 507–508. doi : 10.1038/naturaleza11486. PMID  22972190. S2CID  205230706.
15. Simon, Herbert A. (diciembre de 1955). "Sobre una clase de funciones de distribución sesgada". Biometrika . 42 (3–4): 425–440. doi :10.1093/biomet/42.3-4.425.
16. Precio, DJ de Solla (septiembre de 1976). "Una teoría general de los procesos bibliométricos y otros procesos de ventajas acumulativas". Revista de la Sociedad Estadounidense de Ciencias de la Información . 27 (5): 292–306. CiteSeerX 10.1.1.161.114 . doi :10.1002/asi.4630270505. S2CID  8536863. 
17. Barabási, Albert-László ; Albert, Réka (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.

enlaces externos

• "Este hombre podría gobernar el mundo"
• "Una implementación de Java para Barabási–Albert"
• "Generación de gráficos del modelo Barabási-Albert en código"