Modelo Barabashi-Albert

El modelo Barabashi-Albert (BA) es un algoritmo para generar redes aleatorias sin escala utilizando el principio de conexión preferencial. Las redes libres de escala están muy extendidas en las redes naturales (cadenas alimenticias) y en las redes creadas por el hombre ( Internet , World Wide Web , redes de citas , algunas redes sociales ).

Conceptos

Muchas redes bajo estudio pertenecen a la clase de redes sin escala. Esto significa que tienen una distribución de ley de potencia en grado de nodo, mientras que los modelos de gráficos aleatorios ( Watts-Strogatzy Erdős-Renyi ) no tienen tal distribución. El modelo de Barabasi-Albert es uno de varios modelos de ley de potencia propuestos que generan redes sin escala. Incluye dos conceptos generales importantes:

crecimiento de la red
Principio de apego preferido (PP)

Ambos conceptos están ampliamente representados en las redes del mundo real. Crecimiento significa que el número de nodos de la red aumenta con el tiempo.

El principio de vinculación preferencial es que cuantas más conexiones tenga un nodo, más preferible será que cree nuevas conexiones. Los nodos con mayor grado tienen más oportunidades de hacerse cargo de los enlaces agregados a la red. Intuitivamente, el principio de apego preferencial puede entenderse si pensamos en términos de redes sociales que unen a las personas. Aquí, una conexión de A a B significa que la persona A "conoce" o está "familiarizada" con la persona B. Los nodos fuertemente conectados están representados por personas conocidas con una gran cantidad de conexiones. Cuando un recién llegado entra en la comunidad, es más preferible que se ponga en contacto con una de las personas conocidas que con una relativamente desconocida. De manera similar, en la World Wide Web, las páginas se asocian con centros, como sitios conocidos como Google o Wikipedia , en lugar de páginas que no son muy conocidas. Si se selecciona aleatoriamente una nueva página para vincularla, la probabilidad de elegir una página en particular será proporcional a su grado. Esto explica el principio del apego preferencial.

El principio de vinculación preferencial es un ejemplo de retroalimentación positiva, donde las variaciones inicialmente aleatorias (un nodo inicialmente tiene más enlaces o comienza a recopilar enlaces antes que otros) se amplifican automáticamente, lo que aumenta en gran medida la brecha. Esto también se denomina a veces el efecto Matthew , "los ricos se vuelven más ricos", o autocatálisis en química.

Algoritmo

La red comienza con una malla inicial con nodos. y el grado de cada nodo en la red inicial debe ser al menos 1, de lo contrario siempre estará separado del resto de la red. $m_{0}$ ${\ estilo de visualización m_ {0}> = 2}$

En cada momento, se agrega un nuevo nodo a la red. Cada nuevo nodo se conecta a los nodos existentes con una probabilidad proporcional al número de conexiones de estos nodos. Formalmente, la probabilidad de que un nuevo nodo se conecte al nodo i es: [1] $Pi}$

p_{i}={k_{i} \over\sum_{j}k_{j))

donde es el grado del i-ésimo nodo y el denominador suma los grados de todos los nodos existentes. Los nodos más conectados ("hubs") tienden a acumular aún más conexiones, mientras que es poco probable que se elijan nodos con una pequeña cantidad de conexiones para unirse a nuevos nodos. Los nuevos nodos tienen una "preferencia" para conectarse con los nodos más conectados. $k_i$

Propiedades

Distribución de energía

La distribución de ley de potencias en el modelo BA es libre de escala, más precisamente, obedece a la ley de potencias

{\displaystyle P\left(k\right)\sim k^{-3))

Longitud de ruta promedio

La longitud de ruta promedio en el modelo BA aumenta en promedio como el logaritmo del tamaño de la red. La forma exacta tiene una doble corrección logarítmica [1] y parece

\ell \sim {\frac {\ln N}{\ln \ln N)).

El modelo BA tiene un camino promedio sistemáticamente más corto que un gráfico aleatorio.

Correlaciones de grado de nudo

Las correlaciones de grados de nodos conectados se desarrollan aleatoriamente en el modelo BA, debido a las peculiaridades del desarrollo de la red. La probabilidad de encontrar una conexión entre nodos con grados y en el modelo BA se presenta como

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)}}.

Por supuesto, el resultado será diferente si la distribución no estuviera correlacionada . ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3))$

Coeficiente de agrupamiento

Todavía no hay valores analíticos del coeficiente de agrupamiento del modelo BA. Los coeficientes de agrupamiento obtenidos empíricamente son generalmente mucho más altos para el modelo BA que para las redes aleatorias. El coeficiente de agrupamiento también depende del tamaño de la red según una ley de potencia aproximada:

C\sim N^{-0.75}.

[una]

Este comportamiento sigue siendo diferente del comportamiento de las redes pequeñas, donde el agrupamiento no depende del tamaño de la red. En el caso de redes jerárquicas, el agrupamiento en función del grado de nodo también obedece a una ley de potencia:

C(k)=k^{-1}.

Estos resultados fueron obtenidos analíticamente por Dorogovtsev, Goltsev y Mendes. [3]

Cualidades espectrales

La forma de la densidad espectral del modelo BA difiere de la densidad espectral semicircular de un gráfico aleatorio. Tiene una forma triangular con un vértice mucho más alto que un semicírculo, y los bordes disminuyen de acuerdo con una ley de potencia.

Limitar casos

Modelo A

El modelo A conserva el crecimiento pero no incluye el principio de apego preferencial. La probabilidad de unir un nuevo nodo a los existentes es la misma en todas partes. La distribución de grado finito en este caso sugiere que el crecimiento por sí solo no es suficiente para lograr una estructura sin escala.

Modelo B

El modelo B conserva el principio de apego preferencial pero excluye el crecimiento. El modelo comienza con un número fijo de nodos desconectados y agrega enlaces, eligiendo preferiblemente nodos de alto grado como destinos. Aunque la distribución de energía parece no tener escala al comienzo de la simulación, es inestable y finalmente se vuelve cercana a la gaussiana a medida que la red se acerca a la saturación. Por lo tanto, el principio de PP por sí solo no es suficiente para crear una estructura sin escala. [una]

El fracaso de los modelos A y B para obtener una distribución sin escala sugiere que el crecimiento y la PP son igualmente necesarios para reproducir la distribución estacionaria de ley de potencias que se observa en las redes del mundo real.

Historia

El principio de apego preferencial se utilizó por primera vez para explicar la distribución de la ley de potencias de Yule en 1925 [4] aunque el análisis matemático de Yule se considera oscuro según los estándares modernos debido a la falta de herramientas adecuadas para analizar procesos aleatorios. El método moderno de la ecuación cinética básica, que da una conclusión más transparente, fue aplicado al problema por Herbert Simon en 1955 [5] en el curso del estudio del tamaño de las ciudades y otros fenómenos. Fue aplicado por primera vez al crecimiento de redes por Derek de Solla Price en 1976, [6] quien estaba interesado en las redes de citas entre publicaciones científicas. El nombre de "interconexión preferida" y la popularidad actual de los modelos de red sin escala se deben al trabajo de Albert-Laszlo Barabasi y Reki Albert ., quien descubrió el proceso de forma independiente en 1999 y lo aplicó a la distribución de ley de potencias en la World Wide Web. [2]

Notas

↑ 1 2 3 4 Albert, Reka; R. Alberto; ALABAMA. Barabasi. Mecánica estadística de redes complejas (inglés) // Reseñas de física moderna : revista. - 2002. - vol. 74 . - Pág. 47-97 . -doi : 10.1103 / RevModPhys.74.47 . - . Archivado desde el original el 24 de agosto de 2015.
↑ 1 2 Albert-László Barabási & Reka Albert Emergencia de escalado en redes aleatorias (inglés) // Ciencia : revista. - 1999. - Octubre ( vol. 286 , núm. 5439 ). - Pág. 509-512 . -doi :/ ciencia.286.5439.509 . Archivado desde el original el 17 de abril de 2012.
↑ SN Dorogovtsev, AV Goltsev y JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . Una teoría matemática de la evolución basada en las conclusiones del Dr. JC Willis, FRS // Revista de la Royal Statistical Society : diario. - 1925. - Vol. 88 , núm. 3 . - Pág. 433-436 . -doi : 10.2307/ 2341419 . — .
↑ Herbert A. Simón . Sobre una clase de funciones de distribución sesgada (inglés) // Biometrika : revista. - 1955. - Diciembre ( vol. 42 , no. 3-4 ). - Pág. 425-440 . -doi : 10.1093 / biomet/42.3-4.425 .
↑ DJ de Solla Price . Una teoría general de la bibliometría y otros procesos de ventaja acumulativa (inglés) // Revista de la Sociedad Estadounidense de Ciencias de la Información : diario. - 1976. - vol. 27 . - pág. 292-306 . -doi : 10.1002/ asi.4630270505 .

Enlaces

Redes complejas