Distribución de grados

En el estudio de grafos y redes : el grado de un nodo de red es el número de sus conexiones con otros nodos. La distribución de grados (nodos, vértices) es la distribución de probabilidad de los grados en toda la red.

Definición

El grado de un nodo en una red (a veces incorrectamente confundido con conectividad ) es el número de enlaces o bordes entre ese nodo y otros nodos. Si el gráfico está dirigido , es decir, los bordes tienen direcciones de un nodo a otro, luego los nodos tienen dos valores de grado: grado interior como el número de bordes entrantes y grado exterior como el número de bordes salientes.

La distribución de grados P ( k ) de un grafo se define como la proporción de nodos que tienen grado k . Así, si hay un total de n nodos en la red y n k de ellos tienen grado k , entonces P ( k ) = n k / n .

A veces, la misma información se presenta en forma de una distribución de grado acumulada (esta es la proporción de nodos con un grado inferior a k ) o en forma de una distribución de grado acumulativa complementaria (esta es la proporción de nodos con un grado mayor que k) o igual a k (1 - C , si C es la distribución de grados acumulados ; es decir, complemento de C ).

Distribuciones de potencia observadas

Las distribuciones de grados son muy importantes en la investigación tanto en redes reales, como Internet y las redes sociales , como en redes teóricas. El modelo de red más simple, como un gráfico aleatorio (Bernoulli), en el que cada uno de los n nodos se conecta (o no se conecta) a otros nodos con una probabilidad independiente p (o 1 − p ), tiene una distribución binomial de potencias k :

(o la distribución de Poisson cuando n crece hacia el límite). Sin embargo, las distribuciones de grado de la mayoría de las redes del mundo real difieren significativamente de las anteriores. Muchos de ellos están fuertemente sesgados hacia la derecha, lo que significa que la gran mayoría de los nodos son de bajo grado, pero una pequeña cantidad de nodos, conocidos como "hubs" , son de alto grado. En algunas redes, entre las que merecen especial mención Internet, la World Wide Web y algunas redes sociales, se encuentran distribuciones de potencia que corresponden aproximadamente a una distribución de ley de potencias : P ( k ) ~ k − γ , donde γ es una constante . Este tipo de redes se denominan sin escala y atraen especial atención debido a sus propiedades estructurales y dinámicas. [1] [2] [3] [4]

Véase también

Enlaces

  1. ↑ Barabasi, A.-L. y R. Albert, Science 286 , 509 (1999).
  2. ↑ R. Albert y A. L. Barabási, Phys. Rvdo. Letón. 85 , 5234 (2000).
  3. ↑ SN Dorogovtsev, JFF Mendes y AN Samukhim, cond-mat/0011115.
  4. ↑ Pachón, Angélica; Sacerdote, Laura; Yang, Shuyi. Comportamiento libre de escala de redes con la copresencia de reglas de apego preferenciales y uniformes  // Physica D: Nonlinear  Phenomena : diario. - 2018. - doi : 10.1016/j.physd.2018.01.005 . — . -arXiv : 1704.08597 . _