Modelo de Barabási-Albert

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de red
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neurona artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Bucle Vecindario Camino Vértice Lista  / matriz de adyacencia Listado  / matriz de incidencias Tipos Bipartito Completo Dirigido Hiper Etiquetado Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad Grado Motivo Agrupamiento Distribución de grados Asortatividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős–Rényi Barabási–Albert Bianconi–Barabási Modelo de fitness Watts-Strogatz Aleatorio exponencial (ERGM) Geometría aleatoria (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Modelado de bloques Entropía máxima Configuración suave Punto de referencia LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorías
Temas Software Científicos de redes Categoría:Teoría de redes Categoría:Teoría de grafos
en a mi

El modelo Barabási–Albert (BA) es un algoritmo para generar redes aleatorias sin escala mediante un mecanismo de unión preferencial . Se cree que varios sistemas naturales y artificiales, incluidos Internet , la World Wide Web , las redes de citas y algunas redes sociales , son aproximadamente sin 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 recibe el nombre de sus inventores Albert-László Barabási y Réka Albert .

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

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

El apego preferencial significa que cuanto más conectado esté un nodo, más probabilidades hay de que reciba nuevos enlaces. Los nodos con un grado más alto tienen una mayor capacidad para captar enlaces añadidos a la red. Intuitivamente, el apego preferencial se puede entender si pensamos en términos de redes sociales que conectan a las personas. Aquí un enlace 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 entra en la comunidad, es más probable que se familiarice con una de esas personas más visibles en lugar de con un desconocido relativo. El modelo BA se propuso asumiendo que en la World Wide Web, las páginas nuevas se vinculan preferentemente a centros, es decir, sitios muy conocidos como Google , en lugar de a páginas que casi nadie conoce. Si alguien selecciona una nueva página para vincularse 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 adelante, el modelo de Bianconi-Barabási aborda esta cuestión introduciendo un parámetro de "aptitud". La vinculación 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 ha comenzado a acumular enlaces antes que otro) se refuerzan automáticamente, lo que magnifica enormemente las diferencias. Esto también se denomina a veces efecto Matthew , "los ricos se hacen más ricos ". Véase también autocatálisis .

El único parámetro del modelo BA es , un entero positivo. La red se inicializa con una red de nodos.${\displaystyle m}$${\displaystyle m_{0}\geq m}$

En cada paso, se agrega un nuevo nodo y luego se toman muestras de los vértices existentes de la red, con una probabilidad que es proporcional a la cantidad de enlaces que ya tienen los nodos existentes (los documentos originales no especificaban cómo manejar los casos en los que se elige el mismo nodo existente varias veces). Formalmente, la probabilidad de que el nuevo nodo esté conectado a otro nodo es ^[1].${\displaystyle m}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

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

Los nodos con muchos enlaces ("centros") tienden a acumular rápidamente aún más enlaces, mientras que los nodos con pocos enlaces tienen pocas probabilidades de ser elegidos como destino de un nuevo enlace. Los nuevos nodos tienen una "preferencia" por unirse a los nodos que ya tienen muchos enlaces.

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

${\displaystyle P(k)\sim k^{-3}\,}$

Se demostró que la distribución del índice h o índice de Hirsch también era libre de escala y se propuso como índice de lobby, para ser utilizado como una medida de centralidad ^[2].

${\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 donde${\displaystyle m_{0}=1}$

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

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, , de encontrar un vínculo que conecte un nodo de grado a un nodo antecesor de grado en el modelo BA para el caso especial de (árbol BA) está dada por${\displaystyle n_{k\ell }}$${\displaystyle k}$${\displaystyle \ell }$${\displaystyle m=1}$

${\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íamos . ^[1]${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$

En general , la fracción de enlaces que conectan un nodo de grado a un nodo de grado es ^[3]${\displaystyle m}$${\displaystyle k}$${\displaystyle \ell }$

${\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 , es decir, la distribución de grados de los vecinos de un nodo con grado , viene dada por ^[3]${\displaystyle p(\ell \mid k)}$${\displaystyle k}$

${\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 y luego seleccionamos uno de sus vecinos al azar, la probabilidad de que este vecino seleccionado al azar tenga grado está dada por la expresión anterior.${\displaystyle k}$${\displaystyle \ell }$${\displaystyle p(\ell |k)}$

^{Klemm y Eguíluz [4]} obtuvieron un resultado analítico para el coeficiente de agrupamiento del modelo BA y Bollobás lo demostró. ^[5] Fronczak, Fronczak y Holyst aplicaron un enfoque de campo medio para estudiar el coeficiente de agrupamiento. ^[6]

Este comportamiento es distinto del comportamiento de las redes de mundo pequeño, donde la agrupación es independiente del tamaño del sistema. En el caso de las redes jerárquicas, la agrupación en función del grado de nodo también sigue una ley de potencia,

${\displaystyle C(k)=k^{-1}.\,}$

Este resultado fue obtenido analíticamente por Dorogovtsev, Goltsev y Mendes. ^[7]

La densidad espectral del modelo BA tiene una forma diferente a la densidad espectral semicircular del grafo aleatorio. Tiene forma de triángulo con la parte superior muy por encima del semicírculo y los bordes decaen como una ley de potencia. ^[8] En ^[9] (Sección 5.1), se demostró que la forma de esta densidad espectral no es una función triangular exacta al analizar los momentos de la densidad espectral como una función del exponente de la ley de potencia.

Por definición, el modelo BA describe un fenómeno que se desarrolla en el tiempo y, por lo tanto, además de su propiedad de no tener escala, también se podría buscar su propiedad de escalamiento dinámico. En la red BA, los nodos también se pueden caracterizar por el grado generalizado , el producto de la raíz cuadrada del tiempo de nacimiento de cada nodo y su grado correspondiente , en lugar del grado solo, ya que el tiempo de nacimiento importa en la red BA. Encontramos que la distribución de grado generalizado tiene algunas características no triviales y exhibe escalamiento dinámico.${\displaystyle q}$${\displaystyle k}$${\displaystyle k}$${\displaystyle F(q,t)}$

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

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

El modelo A conserva el crecimiento pero no incluye la unió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, ^[11] lo que indica que el crecimiento por sí solo no es suficiente para producir una estructura libre de escala.

El modelo B conserva la vinculación 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 libre de 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 vinculación preferencial por sí sola no es suficiente para producir una estructura libre de escala.

El fracaso de los modelos A y B para conducir a una distribución libre de escala indica que el crecimiento y la adhesión preferencial son necesarios simultáneamente para reproducir la distribución de ley de potencia estacionaria observada en redes reales. ^[1]

El modelo BA puede considerarse como un caso específico del modelo de apego preferencial no lineal (NLPA) más general. ^[12] 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 es un exponente positivo constante. Si , NLPA se reduce al modelo BA y se denomina "lineal". Si , NLPA se denomina "sublineal" y la distribución de grados de la red tiende a una distribución exponencial estirada . Si , NLPA se denomina "superlineal" y una pequeña cantidad de nodos se conectan a casi todos los demás nodos de la red. Para ambos y , la propiedad de libertad de escala de la red se rompe en el límite del tamaño infinito del sistema. Sin embargo, si es solo ligeramente mayor que , NLPA puede dar como resultado distribuciones de grados que parecen ser transitoriamente libres de escala. ^[13]${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle 0<\alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha }$${\displaystyle 1}$

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. ^[14] 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 ^[15] en el curso de estudios de los tamaños de las ciudades y otros fenómenos. Fue aplicado por primera vez para explicar las frecuencias de citas por Derek de Solla Price en 1976. ^[16] 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 gruesa. En el lenguaje de la red de citas moderna, el modelo de Price produce una red dirigida, es decir, la versión del modelo de Barabási-Albert. El nombre "fijació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 fijación preferencial para explicar las distribuciones de grados observadas numéricamente en la web. ^[17]

• Modelo Bianconi-Barabási
• Proceso de restaurante chino
• Redes complejas
• Modelo Erdős–Rényi (ER)
• Modelo de Price
• Teoría de la percolación
• Red sin escala
• Red de mundo pequeño
• Modelo de Watts y Strogatz

• "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"