Modelo Barabási–Albert

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

El modelo Barabási-Albert (BA) es un algoritmo para generar redes aleatorias sin escala utilizando un mecanismo de conexión preferencial. Se cree que varios sistemas naturales y creados por humanos, incluidos Internet, la World Wide Web, las redes de citas y algunas redes sociales, son aproximadamente libres de 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 lleva el nombre de sus inventores Albert-László Barabási y Réka Albert y es un caso especial de un modelo anterior y más general llamado modelo de Price.

Conceptos

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

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

La vinculación preferencial significa que cuanto más conectado está un nodo, más probable es que reciba nuevos enlaces. Los nodos con un grado más alto tienen una mayor capacidad para capturar enlaces agregados a la red. Intuitivamente, el apego preferencial puede entenderse si pensamos en términos de redes sociales que conectan a las personas. Aquí, un vínculo 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 ingresa a la comunidad, es más probable que se familiarice con una de esas personas más visibles que con un desconocido relativo. El modelo BA se propuso asumiendo que en la World Wide Web, las nuevas páginas enlazan preferentemente con hubs, es decir, sitios muy conocidos como Google, en lugar de páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularla 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 tarde, el modelo Bianconi-Barabási trabaja para abordar este problema al introducir un parámetro de "aptitud". El apego 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 comenzó a acumular enlaces antes que otro) se refuerzan automáticamente, lo que magnifica enormemente las diferencias. Esto también se denomina a veces el efecto Mateo, "los ricos se hacen más ricos". Véase también autocatálisis.

Algoritmo

La red comienza con una red inicial de $m_{0}$ nodos conectados.

Los nuevos nodos se agregan a la red de uno en uno. Cada nuevo nodo se conecta a $mleq m_{0}$ los nodos existentes con una probabilidad proporcional al número de enlaces que ya tienen los nodos existentes. Formalmente, la probabilidad de $Pi}$ que el nuevo nodo esté conectado al nodo $i$ es $p_{i}={frac{k_{i}}{sum_{j}k_{j}}},$

donde $k_{yo}$ es el grado de nodo $i$ y la suma se realiza sobre todos los nodos preexistentes $j$ (es decir, el denominador da como resultado el doble del número actual de aristas en la red). Los nodos muy vinculados ("hubs") tienden a acumular rápidamente aún más enlaces, mientras que es poco probable que los nodos con solo unos pocos enlaces sean elegidos como destino para un nuevo enlace. Los nuevos nodos tienen una "preferencia" para unirse a los nodos ya fuertemente vinculados.

Propiedades

Distribución de grados

La distribución de grados resultante del modelo BA no tiene escala, en particular, es una ley de potencia de la forma $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. $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 de que $m_{0}=1$ $H(1)Grande|_{m_0=1}=4-pi,$

Correlaciones de grado de nodo

Las correlaciones entre los grados de nodos conectados se desarrollan espontáneamente en el modelo BA debido a la forma en que evoluciona la red. La probabilidad, $n_{{kell }}$ , de encontrar un vínculo que conecte un nodo de grado $k$ con un nodo de grado antepasado $ana$ en el modelo BA para el caso especial de $metro=1$ (árbol BA) viene dada por $n_{{kell }}={frac {4left(ell -1right)}{kleft(k+1right)left(k+ell right)left(k+ ell +1right)left(k+ell +2right)}}+{frac {12left(ell -1right)}{kleft(k+ell -1right) izquierda(k+ell right)left(k+ell +1right)left(k+ell +2right)}}.$

Esto confirma la existencia de correlaciones de grado, ya que si las distribuciones no estuvieran correlacionadas, obtendríamos $n_{{kell }}=k^{{-3}}ell ^{{-3}}$ .

En general $metro$ , la fracción de enlaces que conectan un nodo de grado $k$ a un nodo de grado $ana$ es ${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 $p(ell mid k)$ , es decir, la distribución de grados de los vecinos de un nodo con grado $k$ , viene dada por $p(ell mid k)={frac {m(k+2)}{kell (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$ y luego seleccionamos uno de sus vecinos al azar, la probabilidad de que este vecino seleccionado al azar tenga grado $ana$ viene dada por la expresión $p(ell |k)$ anterior.

Coeficiente de agrupamiento

Un resultado analítico para el coeficiente de agrupamiento del modelo BA fue obtenido por Klemm y Eguíluz y probado por Bollobás. Fronczak, Fronczak y Holyst aplicaron un enfoque de campo medio para estudiar el coeficiente de agrupamiento.

Este comportamiento sigue siendo distinto del comportamiento de las redes de mundo pequeño donde el agrupamiento es independiente del tamaño del sistema. En el caso de redes jerárquicas, la agrupación en función del grado de nodo también sigue una ley de potencia, $C(k)=k^{{-1}}.,$

Este resultado fue obtenido analíticamente por Dorogovtsev, Goltsev y Mendes.

Propiedades espectrales

La densidad espectral del modelo BA tiene una forma diferente de la densidad espectral semicircular del gráfico aleatorio. Tiene forma de triángulo con la parte superior situada muy por encima del semicírculo y los bordes decayendo como una ley de potencia.

Escalado dinámico

Por definición, el modelo BA describe un fenómeno de desarrollo temporal y, por lo tanto, además de su propiedad sin escala, también se podría buscar su propiedad de escala dinámica. En la red BA los nodos también se pueden caracterizar por grado generalizado $q$ , el producto de la raíz cuadrada de la hora de nacimiento de cada nodo y su grado correspondiente $k$ , en lugar del grado $k$ solo desde la hora de nacimiento importa en la red BA. Encontramos que la distribución generalizada de grados ${ Displaystyle F (q, t)}$ tiene algunas características no triviales y exhibe una escala dinámica ${displaystyle F(q,t)sim t^{-1/2}phi (q/t^{1/2}).}$

Implica que las gráficas distintas de ${ Displaystyle F (q, t)}$ vs $q$ colapsarían en una curva universal si graficamos ${displaystyle F(q,t)t^{1/2}}$ vs ${displaystyle q/t^{1/2}}$ .

Casos limitantes

Modelo A

El modelo A retiene el crecimiento pero no incluye apego 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, lo que indica que el crecimiento por sí solo no es suficiente para producir una estructura sin escala.

Modelo B

El modelo B conserva el apego 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 no tener 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 unión preferencial por sí sola no es suficiente para producir una estructura sin escamas.

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

Apego preferencial no lineal

El modelo BA se puede considerar como un caso específico del modelo de apego preferencial no lineal (NLPA) más general. 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 $alfa$ es un exponente positivo constante. Si $alfa = 1$ , NLPA se reduce al modelo BA y se denomina "lineal". Si $0<alfa<1$ , NLPA se denomina "sublineal" y la distribución de grados de la red tiende a una distribución exponencial estirada. Si $alfa > 1$ , NLPA se denomina "superlineal" y una pequeña cantidad de nodos se conectan a casi todos los demás nodos de la red. Tanto para como $alfa <1$ para $alfa > 1$ , la propiedad sin escala de la red se rompe en el límite del tamaño infinito del sistema. Sin embargo, si $alfa$ es solo un poco más grande que $1$ , NLPA puede dar como resultado distribuciones de grados que parecen estar transitoriamente libres de escala.

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. El método moderno de la ecuación maestra, que produce una derivación más transparente, fue aplicado al problema por Herbert A. Simon en 1955 en el curso de estudios de los tamaños de las ciudades y otros fenómenos. Fue aplicado por primera vez al crecimiento de las redes por Derek de Solla Price en 1976.Price estaba interesado en las redes de citas entre artículos científicos y el modelo de Price utilizó la "ventaja acumulativa" (su nombre para el apego preferencial) para producir una red dirigida, por lo que el modelo de Barabási-Albert es una versión no dirigida del modelo de Price. El nombre de "conexión preferencial" y la popularidad actual de los modelos de red sin escala se debe al trabajo de Albert-László Barabási y Réka Albert, quienes redescubrieron el proceso de forma independiente en 1999 y lo aplicaron a las distribuciones de títulos en la web.

Contenido relacionado

Más resultados...