Modelo Barabási–Albert

Red de 1000 nodos generada con el modelo de Modelo de Barabási–Albert

En teoría de redes se denomina Modelo de Barabási–Albert (es posible encontrarlo en la literatura abreviadamente como modelo BA) como un algoritmo empleado para generar redes aleatorias complejas libres de escala empleando una regla o mecanismo denominado conexión preferencial. Las redes generadas por este algoritmo poseen una distribución de grado de tipo potencial y que se denominan: "redes libres de escalas. Las redes de este tipo son muy frecuentes en los sistemas elaborados por el ser humano así como en la naturaleza. Ejemplos de sistemas de este tipo son Internet, el world wide web, redes de citas, y algunas redes sociales, redes eléctricas.^[1] El modelo toma el nombre de Albert-László Barabási y Réka Albert autores que lo popularizaron en 1999.^[2]

Concepto

Muchas de las redes observadas en la naturaleza caen dentro de la clase denominada como "redes libres de escala", esta afirmación viene a decir que sus distribuciones de grado siguen leyes exponenciales (o libres de escala), mientras que otros modelos de grafos aleatorios tal y como el modelo Erdős–Rényi (ER) y el de Watts-Strogatz (WS) no exhiben tal característica de ley de potencias. El modelo de Barabási–Albert model es uno de los propuestos para la generación de redes libres de escala. Incorpora dos conceptos generales: crecimiento y conexión preferencial (preferential attachment). Ambos conceptos pueden encontrarse extensivamente en las redes reales que nos rodean. La propiedad de creciemiento en teoría de redes significa que las redes poseen una cantidad de nodos creciente.

Algoritmo

Red construida según el modelo Barabási–Albert, se puede ver como algunos nodos "coleccionan" la mayoría de las conexiones.

La red comienza con un conjunto de m₀ nodos conectados aleatoriamente. Debe notarse que $m_0\geq 2$ * y el grado de cada nodo en la red inicial debe ser al menos 1, de otra forma la evolución de la red, a medida que se van añadiendo nodos, haría que éstos permanecieran desconectados completamente de la red.

- * En el escrito orginial de Barabasi-Albert "Emergence of scaling in complex networks" se habla sobre agregar un nodo con m aristas donde (m<=mo) y no se especifica que se debe de agregar solamente un enlace por nodo.

Los nuevos nodos se añaden a la red de uno a uno. Cada nodo es conectado a m nodos de la red con una probabilidad que es proporcional al número de enlaces que posee los nodos de la red, es decir, los nuevos nodos se enlazan preferiblemente con los nodos más conectados. Formalmente la probabilidad p_i de que un nuevo nodo se conecte con i es:^[3]

$p_i = \frac{k_i}{\displaystyle\sum_j k_j}$,

donde k_i es el grado del nodo i. Los nodos con gran cantidad de conexiones ("hubs") tienden a acumular rapidamente más enlaces, mientras que los que poseen pocos enlaces rara vez son el origen de nuevos enlaces. Los nuevos nodos según este algoritmo se dice que poseen una "preferencia" a ser enlazados con los nodos más solicitados. Este algoritmo se fundamenta en el concepto de "conexión prefencial" de los nuevos nodos que se incorporan a la red.

Este algoritmo se diferencia cláramente del modelo Erdös–Rényi en que los nodos poseen una característica que los hace "distinguibles" en el número de enlaces. No obstante ambos son algoritmos válidos para la generación de redes de pequeño mundo.

Historia

El primer uso del concepto conexión preferencial para explicar las distribuciones exponenciales aparece ser atribuido a Yule en el año 1925,^[4] debido a que los tratamientos matemáticos de Yule fueron opacos a la comunidad científica debido en parte al poco uso de herramientas estándares de análisis de procesos estocásticos, el descubrimiento se quedó en el olvido durante algunos años. Los modernos métodos aplicados por Herbert Simon en el año 1955 dejaron una mayor comprensión del fenómeno.^[5] Estos procesos dieron paso al análisis de otros fenómenos. Fue aplicado por primera vez al crecimiento de redes por Derek de Solla Price en 1976^[6] que fue quien estaba interesado en redes de citas entre artículos de revistas científicas. El nombre de conexión preferencial ("preferential attachment") y su popularidad posterior en los modelos de redes libres de escala se debe al trabajo de Albert-László Barabási y Réka Albert, que fueron los re-descubridores del proceso en 1999 y lo aplicaron a la distribución del número de enlaces (links) que tiene cada sitio de Internet.^[2]

Problemas

El modelo presenta algunos problemas que fueron refinados posteriormente, uno de ellos tiene nombre definido por el propio Albert Barbási: "Fit get richer" ("el más apto se hace más rico"). Este problema aparece en la evolución de algunas redes ya que los vértices con alta conectividad se hacen cada vez más "ricos" en conexiones a medida que avanza la evolución de la red. Este problema se soslaya con otra tendencia que se denomina "fitness" y es que a veces algunos nodos poseen una capacidad de conexión preferencial que varía con el tiempo.

Propiedades

• Genera redes con distribución de grado exponencial de la forma:

$\textstyle P(k) = k^{-\gamma}$

Donde $\textstyle \gamma > 0$

Véase también

• Red libre de escala
• Ley de Zipf
• Condensado Bose-Einstein en redes

Referencias

1. ↑ "Evaluating North American Electric Grid Reliability Using the Barabási-Albert Network Model", David P. Chassin, Christian Posse, 2005 Elsevier Science B.V
2. ↑ ^{a b} Albert-László Barabási & Réka Albert (October 1999). «Emergence of scaling in random networks». Science 286:  pp. 509–512. doi:10.1126/science.286.5439.509. http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf. 
3. ↑ R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics, Vol 74, page 47-97, 2002.
4. ↑ Udny Yule (1925). «A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S.». Journal of the Royal Statistical Society 88:  pp. 433-436. 
5. ↑ Herbert A. Simon (December 1955). «On a Class of Skew Distribution Functions». Biometrika 42 (3-4):  pp. 425–440. doi:10.1093/biomet/42.3-4.425. 
6. ↑ D.J. de Solla Price (1976). «A general theory of bibliometric and other cumulative advantage processes». Journal of the American Society for Information Science 27:  pp. 292-306. doi:10.1002/asi.4630270505.