Model Barabási–Albert

Archiu:Barabasi Albert 1000nodes.png

Ret de 1000 nodos generada en el model de Model de Barabási–Albert

En teoria de rets es denomina Model de Barabási–Albert (és possible trobar-ho en la lliteratura abreviadamente com a model BA) com un algoritme amprat per a generar rets aleatòries complexes lliures d'escala amprant una regla o mecanisme denominat conexió preferencial. Les rets generades per este algoritme posseïxen una distribució de grau de tipo potencial i es denominen: rets lliures d'escales. Les rets d'este tipo són molt freqüents en els sistemes elaborats pel ser humà aixina com en la naturalea. Eixemples de sistemes d'este tipo són Internet, el world wide web, rets de cites, i algunes rets socials, rets elèctriques. El model pren el nom d'Albert-László Barabási i Réka Albert autors que ho varen popularisar en 1999.

Concepte

Moltes de les rets observades en la naturalea cauen dins de la classe denominada com "rets lliures d'escala", esta afirmació ve a dir que les seues distribucions de grau seguixen lleis de potències (o lliures d'escala), mentres que atres models de grafos aleatoris tal i com el model Erdős–Rényi (ER) i el de Watts-Strogatz (WS) no exhibixen tal característica de llei de potències. El model de Barabási–Albert és un dels proposts per a la generació de rets lliures d'escala. Incorpora dos conceptes generals: creiximent i conexió preferencial (preferential attachment). Abdós conceptes poden trobar-se extensivamente en les rets reals que nos rodegen. La propietat de creiximent en teoria de rets significa que les rets posseïxen una cantitat de nodos creixent.

Algoritme

Archiu:Complex network n25 BAmodel.png

Ret construïda segons el model Barabási–Albert, es pot vore com alguns nodos "coleccionen" la majoria de les conexions.

La ret comença en un conjunt de $m_0$ nodos conectats aleatoriamente. Deu notar-se que $m_0\ge 2$ * i el grau de cada nodo en la ret inicial deu ser a lo manco 1, d'una atra forma l'evolució de la ret, a mida que es van afegint nodos, faria que estos permaneixqueren desconectats completament de la ret.

En l'escrit orginial de Barabasi-Albert "Emergence of scaling in complex networks" es parla sobre agregar un nodo en m arestes a on (m<=mo) i no s'especifica que es deu agregar solament un enllaç per nodo.

Els nous nodos s'afigen a la ret d'un a un. Cada nodo és conectat a $m$ nodos de la ret en una provabilitat que és proporcional al número d'enllaços que posseïx els nodos de la ret, és dir, els nous nodos s'enllacen preferiblement en els nodos més conectats. Formalment la provabilitat $p_i$ de que un nou nodo es conecte en i és:

$p_i=\frac{k_i}{\sum _j{k}_j}$,

a on $k_i$ és el grau del nodo i. Els nodos en gran cantitat de conexions ("hubs") tendixen a acumular ràpidament més enllaços, mentres que els que posseïxen pocs enllaços rara volta són l'orige de nous enllaços. Els nous nodos segons este algoritme es diu que posseïxen una "preferència" a ser enllaçats en els nodos més solicitats. Este algoritme es fonamenta en el concepte de "conexió prefencial" dels nous nodos que s'incorporen a la ret.

Este algoritme es diferencia clarament del model Erdös–Rényi que els nodos posseïxen una característica que els fa "distinguibles" en el número d'enllaços. No obstant abdós són algoritmes vàlits per a la generació de rets de chicotet món.

Vore també

• Ret lliure d'escala
• Llei de Zipf
• Condensado Bose-Einstein en rets