Modelo de Barabási-Albert

Algoritmo de generación de redes sin escala

Representación de tres gráficos generados con el modelo Barabasi-Albert (BA). Cada uno tiene 20 nodos y un parámetro de unión m según lo especificado. 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 mediante un mecanismo de unión preferencial . Se cree que varios sistemas naturales y artificiales, incluidos Internet , la World Wide Web , las redes de citas y algunas redes sociales , son aproximadamente sin escala y ciertamente contienen pocos nodos (llamados concentradores) con un grado inusualmente alto en comparación con los otros nodos de la red. El modelo BA intenta explicar la existencia de tales nodos en redes reales. El algoritmo recibe el nombre de sus inventores Albert-László Barabási y Réka Albert .

Conceptos

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

Crecimiento significa que el número de nodos en la red aumenta con el tiempo.

El apego preferencial significa que cuanto más conectado esté un nodo, más probabilidades hay de que reciba nuevos enlaces. Los nodos con un grado más alto tienen una mayor capacidad para captar enlaces añadidos a la red. Intuitivamente, el apego preferencial se puede entender si pensamos en términos de redes sociales que conectan a las personas. Aquí un enlace de A a B significa que la persona A "conoce" o "está familiarizada con" la persona B. Los nodos fuertemente vinculados representan a personas conocidas con muchas relaciones. Cuando un recién llegado entra en la comunidad, es más probable que se familiarice con una de esas personas más visibles en lugar de con un desconocido relativo. El modelo BA se propuso asumiendo que en la World Wide Web, las páginas nuevas se vinculan preferentemente a centros, es decir, sitios muy conocidos como Google , en lugar de a páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularse 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 apego preferencial.

Más adelante, el modelo de Bianconi-Barabási aborda esta cuestión introduciendo un parámetro de "aptitud". La vinculación 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 que ha comenzado a acumular enlaces antes que otro) se refuerzan automáticamente, lo que magnifica enormemente las diferencias. Esto también se denomina a veces efecto Matthew , "los ricos se hacen más ricos ". Véase también autocatálisis .

Algoritmo

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

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

En cada paso, se agrega un nuevo nodo y luego se toman muestras de los vértices existentes de la red, con una probabilidad que es proporcional a la cantidad de enlaces que ya tienen los nodos existentes (los documentos originales no especificaban cómo manejar los casos en los que se elige el mismo nodo existente varias veces). Formalmente, la probabilidad de que el nuevo nodo esté conectado a otro 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 primero muestreando uniformemente una arista y luego muestreando uno de los dos vértices de la arista. ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\displaystyle j}$

Los nodos con muchos enlaces ("centros") tienden a acumular rápidamente aún más enlaces, mientras que los nodos con pocos enlaces tienen pocas probabilidades de ser elegidos como destino de un nuevo enlace. Los nuevos nodos tienen una "preferencia" por unirse a los nodos que ya tienen muchos enlaces.

Red arbórea 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

Distribución de los grados de los vértices de un grafo BA con 200000 nodos y 2 aristas nuevas por paso. Representada en escala logarítmica. Sigue una ley de potencia con exponente -2,78.

La distribución de grados resultante del modelo BA es libre de 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 era libre de escala y se propuso como índice de lobby, para ser utilizado como una 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 donde ${\displaystyle m_{0}=1}$

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

Correlaciones de grado de nodo

Las correlaciones entre los grados de los 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 a un nodo antecesor 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 a 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 está 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 Bollobás lo demostró. ^[5] Fronczak, Fronczak y Holyst aplicaron un enfoque de campo medio para estudiar el coeficiente de agrupamiento. ^[6]

Este comportamiento es distinto del comportamiento de las redes de mundo pequeño, donde la agrupación es independiente del tamaño del sistema. En el caso de las 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 grafo aleatorio. Tiene forma de triángulo con la parte superior muy por encima del semicírculo y los bordes decaen 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 al analizar los momentos de la densidad espectral como una función del exponente de la ley de potencia.

Escalamiento dinámico

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

Los mismos datos se grafican en coordenadas autosimilares y brindan una excelente revelación colapsada que exhibe 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 de no tener escala, también se podría buscar su propiedad de escalamiento dinámico. 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 grado generalizado tiene algunas características no triviales y exhibe escalamiento dinámico. ${\displaystyle q}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle F(q,t)}$

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

Esto implica que las distintas gráficas de vs colapsarían en una curva universal si graficamos 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 la unión 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 libre de escala.

Modelo B

El modelo B conserva la vinculación 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 finalmente se vuelve casi gaussiana a medida que la red se acerca a la saturación. Por lo tanto, la vinculación preferencial por sí sola no es suficiente para producir una estructura libre de escala.

El fracaso de los modelos A y B para conducir a una distribución libre de escala indica que el crecimiento y la adhesión preferencial son necesarios simultáneamente para reproducir la distribución de ley de potencia estacionaria observada en redes reales. ^[1]

Fijación preferencial no lineal

El modelo BA puede considerarse como un caso específico del modelo de apego preferencial no lineal (NLPA) más general. ^[12] El algoritmo NLPA es idéntico al modelo BA con la probabilidad de apego 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 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. ^[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 de los tamaños de las ciudades y otros fenómenos. Fue aplicado por primera vez para explicar las frecuencias de citas por Derek de Solla Price en 1976. ^[16] Price estaba interesado en la acumulación de citas de artículos científicos y el modelo de Price utilizó la "ventaja acumulativa" (su nombre para el apego preferencial) para generar una distribución de cola gruesa. En el lenguaje de la red de citas moderna, el modelo de Price produce una red dirigida, es decir, la versión del modelo de Barabási-Albert. El nombre "fijación preferencial" y la popularidad actual de los modelos de redes libres de escala se deben 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 la fijación preferencial para explicar las distribuciones de grados observadas numéricamente en la web. ^[17]

Véase también

• Modelo Bianconi-Barabási
• Proceso de restaurante chino
• Redes complejas
• Modelo Erdős–Rényi (ER)
• Modelo de Price
• Teoría de la percolación
• Red sin escala
• Red de 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". Physica A . 388 (11): 2221–2226. arXiv : 0809.0514 . Código Bibliográfico :2009PhyA..388.2221K. doi :10.1016/j.physa.2009.02.013. S2CID  1119190.
3. Fotouhi, Babak; Rabbat, Michael (2013). "Correlación de grados en grafos sin escala". The European Physical Journal B . 86 (12): 510. arXiv : 1308.5169 . Código Bibliográfico :2013EPJB...86..510F. doi :10.1140/epjb/e2013-40920-6. S2CID  7520124.
4. Klemm, K.; Eguíluz, VC (2002). "Crecimiento de redes libres de escala con comportamiento de mundo pequeño". Physical Review E . 65 (5): 057102. arXiv : cond-mat/0107607 . Bibcode :2002PhRvE..65e7102K. doi :10.1103/PhysRevE.65.057102. hdl :10261/15314. PMID  12059755. S2CID  12945422.
5. Bollobás, B. (2003). "Resultados matemáticos en grafos aleatorios libres de escala". Manual de grafos y redes . págs. 1–37. CiteSeerX 10.1.1.176.6988 . 
6. Fronczak, Agata; Fronczak, Piotr; Hołyst, Janusz A (2003). "Teoría del campo medio para coeficientes de agrupamiento en redes de Barabasi-Albert". Phys. 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). "Red libre de escala pseudofractal". Physical Review 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 grafos del "mundo real": más allá de la ley del semicírculo". Physical Review E . 64 (2): 026704. arXiv : cond-mat/0102335 . Bibcode :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". IEEE Transactions on Network Science and Engineering . 4 (4): 215–228. arXiv : 1512.03489 . doi : 10.1109/TNSE.2017.2712064 . S2CID  12187100.
10. MK Hassan, MZ Hassan y NI Pavel, “Escalamiento dinámico, colapso de datos y autosimilitud en redes Barabasi-Albert” J. Phys. A: Math. Theor. 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 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". 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.
13. 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.
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. Price, DJ de Solla (septiembre de 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. 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"