Hispanopedia Wiki
Articulo de referencia

Modelo de Barabási-Albert

Visualización de tres grafos generados con el modelo de Barabási-Albert (BA). Cada uno tiene 20 nodos y un parámetro de conexión m, según lo especificado. El color de cada nodo ...

Hispanopedia WikiContenido en espanolLectura gratuita
Visualización de tres grafos generados con el modelo de Barabási-Albert (BA). Cada uno tiene 20 nodos y un parámetro de conexión m, según lo especificado. El color de cada nodo depende de su grado (misma escala para cada grafo).

El modelo de Barabási-Albert (BA) es un algoritmo para generar redes aleatorias libres de escala mediante un mecanismo de conexión preferencial . Se cree que varios sistemas naturales y artificiales, como Internet , la World Wide Web , las redes de citas y algunas redes sociales , son aproximadamente libres de escala y, sin duda, contienen pocos nodos (denominados hubs) con un grado inusualmente alto en comparación con los demás nodos de la red. El modelo BA intenta explicar la existencia de dichos nodos en redes reales. El algoritmo recibe su nombre de sus inventores, Albert-László Barabási y Réka Albert .

Conceptos

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

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

La conexión preferencial implica que cuanto más conectado esté un nodo, mayor será la probabilidad de que reciba nuevos enlaces. Los nodos con un grado más alto tienen mayor capacidad para captar enlaces añadidos a la red. Intuitivamente, la conexión preferencial se puede comprender si pensamos en términos de redes sociales que conectan personas. En este caso, un enlace de A a B significa que la persona A "conoce" o "tiene alguna relación" con la persona B. Los nodos con muchos enlaces representan a personas conocidas con numerosas relaciones. Cuando un recién llegado se incorpora a la comunidad, es más probable que se relacione con una de esas personas más visibles que con una persona relativamente desconocida. El modelo BA se propuso asumiendo que, en la World Wide Web, las nuevas páginas enlazan preferentemente a hubs, es decir, a sitios muy conocidos como Google , en lugar de a páginas que casi nadie conoce. Si alguien selecciona una nueva página para enlazar 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 conexión preferencial.

Posteriormente, el modelo de Bianconi-Barabási aborda este problema introduciendo un parámetro de "aptitud". La conexión preferencial es un ejemplo de un ciclo de retroalimentación positiva donde las variaciones inicialmente aleatorias (un nodo que inicialmente tiene más enlaces o que comenzó a acumularlos antes que otro) se refuerzan automáticamente, magnificando así enormemente las diferencias. Esto también se conoce como el efecto Mateo , "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 de Barabási-Albert (metro0=metro=2{\displaystyle m_{0}=m=2})

El único parámetro en el modelo BA esmetro{\displaystyle m}, un entero positivo. La red se inicializa con una red demetro0≥metro{\displaystyle m_{0}\geq m}nodos.

En cada paso, agregue un nuevo nodo y luego realice un muestreo.metro{\displaystyle m}vecinos entre los vértices existentes de la red, con una probabilidad que es proporcional al número de enlaces que los nodos existentes ya tienen (Los artículos originales no especificaban cómo manejar los casos en los que se elige el mismo nodo existente varias veces). Formalmente, la probabilidadpagi{\displaystyle p_{i}}que el nuevo nodo está conectado al nodoi{\displaystyle i}es [ 1 ]

pagi=ki∑jkj,{\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}

dóndeki{\displaystyle k_{i}}es el grado del nodoi{\displaystyle i}y la suma se realiza sobre todos los nodos preexistentes.j{\displaystyle j}(es decir, el denominador resulta en el doble del número actual de aristas en la red). Este paso se puede realizar muestreando primero uniformemente una arista y luego muestreando uno de los dos vértices de dicha arista.

Los nodos con muchos enlaces ("hubs") tienden a acumular rápidamente aún más enlaces, mientras que es improbable que los nodos con pocos enlaces sean elegidos como destino para un nuevo enlace. Los nuevos nodos tienen una "preferencia" por conectarse a los nodos que ya tienen muchos enlaces.

Una red de árbol generada según el modelo de Barabási-Albert. La red está compuesta por 50 vértices conmetro=1{\displaystyle m=1}.

Propiedades

Distribución de grados

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

La distribución de grados resultante del modelo BA es libre de escala, en particular, es una ley de potencias de la forma

PAG(k)∼k−3{\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 es libre de escala y se propuso como el índice de lobby, para ser utilizado como una medida de centralidad [ 2 ].

H(k)∼k−6{\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 dondemetro0=1{\displaystyle m_{0}=1}

H(1)|metro0=1=4−π{\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,nortekℓ{\displaystyle n_{k\ell }}, de encontrar un enlace que conecte un nodo de grado k{\displaystyle k}a un nodo ancestral de grado ℓ{\displaystyle \ell }en el modelo BA para el caso especial demetro=1{\displaystyle m=1}(Árbol BA) viene dado por

nortekℓ=4(ℓ−1)k(k+1)(k+ℓ)(k+ℓ+1)(k+ℓ+2)+12(ℓ−1)k(k+ℓ−1)(k+ℓ)(k+ℓ+1)(k+ℓ+2).{\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íamosnortekℓ=k−3ℓ−3{\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}. [ 1 ]

Para generalmetro{\displaystyle m}, la fracción de enlaces que conectan un nodo de gradok{\displaystyle k} a un nodo de grado ℓ{\displaystyle \ell }es [ 3 ]

pag(k,ℓ)=2metro(metro+1)k(k+1)ℓ(ℓ+1)[1−(2metro+2metro+1)(k+ℓ−2metroℓ−metro)(k+ℓ+2ℓ+1)].{\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 del grado del vecino más cercanopag(ℓ∣k){\displaystyle p(\ell \mid k)}, es decir, la distribución de grados de los vecinos de un nodo con gradok{\displaystyle k}, viene dado por [ 3 ]

pag(ℓ∣k)=metro(k+2)kℓ(ℓ+1)[1−(2metro+2metro+1)(k+ℓ−2metroℓ−metro)(k+ℓ+2ℓ+1)].{\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 k{\displaystyle k}y luego seleccionar uno de sus vecinos al azar, la probabilidad de que este vecino seleccionado al azar tenga gradoℓ{\displaystyle \ell }viene dada por la expresiónpag(ℓ|k){\displaystyle p(\ell |k)}arriba.

Coeficiente de agrupamiento

El caso de metro=1{\displaystyle m=1}Es trivial: las redes son árboles y el coeficiente de agrupamiento es igual a cero. Klemm y Eguíluz obtuvieron un resultado analítico para el coeficiente de agrupamiento del modelo BA [ 4 ] , el cual fue demostrado por Bollobás [ 5 ] . Fronczak, Fronczak y Holyst aplicaron un enfoque de campo medio para estudiar el coeficiente de agrupamiento [ 6 ] .

El coeficiente de agrupamiento promedio del modelo de Barabási-Albert depende del tamaño de la red N:

⟨do⟩∼lnortenorte2/norte.{\displaystyle \langle C\rangle \sim lnN^{2}/N.}

Este comportamiento es distinto al de las redes de mundo pequeño, donde la agrupación es independiente del tamaño del sistema.

La agrupación en función del grado del nododo(k){\displaystyle C(k)} es prácticamente independiente dek{\displaystyle k}. [ 6 ]

Propiedades espectrales

La densidad espectral del modelo BA tiene una forma diferente a la densidad espectral semicircular de un grafo aleatorio. Tiene una forma triangular, con el vértice situado muy por encima del semicírculo y los bordes decayendo según una ley de potencias. [ 7 ] En [ 8 ] (Sección 5.1), se demostró que la forma de esta densidad espectral no es una función triangular exacta mediante el análisis de los momentos de la densidad espectral en función del exponente de la ley de potencias.

Casos limitantes

Modelo A

El modelo A conserva el crecimiento, pero no incluye la conexió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, [ 9 ] 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 conexión preferencial, pero elimina el crecimiento. Comienza con un número fijo de nodos desconectados y añade enlaces, seleccionando preferentemente nodos de alto grado como destinos. Si bien la distribución de grados al inicio de la simulación parece libre de escala, no es estable y, con el tiempo, se vuelve casi gaussiana a medida que la red se acerca a la saturación. Por lo tanto, la conexión preferencial por sí sola no es suficiente para generar una estructura libre de escala.

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

Adhesión preferencial no lineal

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

pagi=kiα∑jkjα,{\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}},}

dóndeα{\displaystyle \alpha }es un exponente positivo constante. Siα=1{\displaystyle \alpha =1}NLPA se reduce al modelo BA y se denomina "lineal". Si0<α<1{\displaystyle 0<\alpha <1}NLPA se denomina "sublineal" y la distribución de grados de la red tiende a una distribución exponencial estirada .α>1{\displaystyle \alpha >1}NLPA se denomina "superlineal" y un pequeño número de nodos se conecta a casi todos los demás nodos de la red. Para ambosα<1{\displaystyle \alpha <1}yα>1{\displaystyle \alpha >1}, la propiedad de escala libre de la red se rompe en el límite de tamaño infinito del sistema. Sin embargo, siα{\displaystyle \alpha }es solo un poco más grande que1{\displaystyle 1}NLPA puede dar como resultado distribuciones de grado que parecen ser transitoriamente libres de escala. [ 11 ]

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. [ 12 ] 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 [ 13 ] en el curso de estudios sobre el tamaño de las ciudades y otros fenómenos. Fue aplicado por primera vez para explicar las frecuencias de citación por Derek de Solla Price en 1976. [ 14 ] 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 pesada. 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 "conexió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 conexión preferencial para explicar las distribuciones de grado observadas numéricamente en la web. [ 15 ]

Véase también

Referencias

  1. 1 2 3 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 . Bibcode : 2009PhyA..388.2221K . doi : 10.1016/j.physa.2009.02.013 . S2CID 1119190 . 
  3. 1 2 Fotouhi, Babak; Rabbat, Michael (2013). "Correlación de grado en grafos libres de escala". The European Physical Journal B . 86 (12): 510. arXiv : 1308.5169 . Bibcode : 2013EPJB...86..510F . doi : 10.1140/epjb/e2013-40920-6 . S2CID 7520124 . 
  4. ↑ Klemm, K.; Eguíluz, VC (2002). "Growing scale-free networks with small-world behavior". 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 sobre grafos aleatorios libres de escala". Manual de grafos y redes . págs. 1–37 . CiteSeerX 10.1.1.176.6988 .  
  6. 1 2 Fronczak, Agata; Fronczak, Piotr; Hołyst, Janusz A (2003). "Teoría de campo medio para coeficientes de agrupamiento en redes de Barabasi-Albert". Phys. Rev. E . 68 (4) 046126. arXiv : cond-mat/0306255 . Bibcode : 2003PhRvE..68d6126F . doi : 10.1103/PhysRevE.68.046126 . PMID 14683021 . S2CID 2372695 .  
  7. ↑ 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". 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 .  
  8. ↑ Preciado, VM; Rahimian, A. (diciembre de 2017). "Análisis espectral basado en momentos de grafos aleatorios con una secuencia de grados esperados dada" . IEEE Transactions on Network Science and Engineering . 4 (4): 215– 228. arXiv : 1512.03489 . doi : 10.1109/TNSE.2017.2712064 . S2CID 12187100 . 
  9. ↑ Pekoz, Erol; Rollin, A.; Ross, N. (2012). "Variación total y límites de error locales para la aproximación geométrica" . Bernoulli . Archivado del original el 23 de septiembre de 2015. Recuperado el 25 de octubre de 2012 .
  10. ↑ 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 . Bibcode : 2000PhRvL..85.4629K . doi : 10.1103 /PhysRevLett.85.4629 . PMID 11082613. S2CID 16251662 .  
  11. ↑ Krapivsky, Paul; Krioukov, Dmitri (21 de agosto de 2008). "Redes libres de escala como regímenes preasintóticos de conexió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 .  
  12. ^ Albert-László, Barabási (2012). "Suerte o razón". Naturaleza . 489 (7417): 507– 508. doi : 10.1038/naturaleza11486 . PMID 22972190 . S2CID 205230706 .  
  13. ↑ Simon, Herbert A. (diciembre de 1955). "Sobre una clase de funciones de distribución asimétricas". Biometrika . 42 ( 3–4 ): 425–440 . doi : 10.1093/biomet/42.3-4.425 .
  14. ↑ Price, DJ de Solla (septiembre de 1976). "Una teoría general de los procesos de ventaja acumulativa bibliométrica y de otro tipo". Journal of the American Society for Information Science . 27 (5): 292– 306. CiteSeerX 10.1.1.161.114 . doi : 10.1002/asi.4630270505 . S2CID 8536863 .  
  15. ↑ 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 : 1999Sci...286..509B . doi : 10.1126/ciencia.286.5439.509 . PMID 10521342 . S2CID 524106 . Archivado desde el original (PDF) el 17 de abril de 2012.  
  • "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"
Obtenido de " https://en.wikipedia.org/w/index.php?title=Barabási–Albert_model&oldid=1315229424 "
Lecturas relacionadas
6 articulos
Mapa de Internet 1024.jpgRed complejaEn el contexto de la teoría de redes , una red compleja es un grafo (red) con características topológicas no triviales , características que no ocu...Red sin escalaRed sin escalaDistribución de grados para una red con 150.000 vértices y grado medio = 6 creada mediante el modelo de Barabási–Albert (puntos azules). La distrib...Apego preferencialGráfico generado mediante unión preferencial. Una pequeña cantidad de nodos tiene una gran cantidad de aristas entrantes, mientras que una gran can...InternetInternetInternet (o internet ) [a] es el sistema global de redes de computadoras interconectadas que utiliza el conjunto de protocolos de Internet (TCP/IP)...World Wide WebWorld Wide WebUna página web de Wikipedia mostrada en Google Chrome La World Wide Web ( WWW o simplemente la Web ) es un sistema de información que permite compa...Análisis de citasEl análisis de citas es el examen de la frecuencia, los patrones y los gráficos de citas en documentos. Utiliza el gráfico dirigido de citas (enlac...