Distribución de grados

En el estudio de grafos y redes , el grado de un nodo en una red es el número de conexiones que tiene con otros nodos, y la distribución de grados es la distribución de probabilidad de estos grados en toda la red.

El grado de un nodo en una red (a veces denominado incorrectamente conectividad ) es el número de conexiones o aristas que tiene con otros nodos. Si una red es dirigida , es decir, si las aristas apuntan en una sola dirección de un nodo a otro, entonces los nodos tienen dos grados diferentes: el grado de entrada, que es el número de aristas entrantes, y el grado de salida, que es el número de aristas salientes.

La distribución de grados P ( k ) de una red se define entonces como la fracción de nodos en la red con grado k . Por lo tanto, si hay n nodos en total en una red y n _k de ellos tienen grado k , tenemos

${\displaystyle P(k)={\frac {n_{k}}{n}}}$.

La misma información también se presenta a veces en forma de una distribución de grado acumulativa , la fracción de nodos con grado menor que k , o incluso la distribución de grado acumulativa complementaria , la fracción de nodos con grado mayor o igual a k (1 - C ) si se considera C como la distribución de grado acumulativa ; es decir , el complemento de C.

La distribución de grados es muy importante para estudiar tanto redes reales, como Internet y las redes sociales , como redes teóricas. El modelo de red más simple, por ejemplo, el grafo aleatorio (modelo de Erdős-Rényi) , en el que cada uno de los n nodos está conectado (o no) independientemente con una probabilidad p (o 1 − p ), tiene una distribución binomial de grados k :

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(o Poisson en el límite de n grande , si el grado promedio${\displaystyle \langle k\rangle =p(n-1)}$se mantiene fijo). Sin embargo, la mayoría de las redes del mundo real tienen distribuciones de grado muy diferentes a esta. La mayoría están muy sesgadas hacia la derecha , lo que significa que una gran mayoría de nodos tienen un grado bajo, pero un pequeño número, conocidos como "hubs", tienen un grado alto. Se ha argumentado que algunas redes, en particular Internet, la World Wide Web y algunas redes sociales, tienen distribuciones de grado que siguen aproximadamente una ley de potencias :${\displaystyle P(k)\sim k^{-\gamma }}$donde γ es una constante. Estas redes se denominan redes libres de escala y han atraído especial atención por sus propiedades estructurales y dinámicas. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

La distribución de grado excedente es la distribución de probabilidad, para un nodo alcanzado al seguir una arista, del número de otras aristas conectadas a ese nodo. ^{[ 5 ]} En otras palabras, es la distribución de enlaces salientes desde un nodo alcanzado al seguir un enlace.

Supongamos que una red tiene una distribución de grados${\displaystyle P(k)}$, seleccionando un nodo (aleatoriamente o no) y yendo a uno de sus vecinos (suponiendo que tenga al menos un vecino), entonces la probabilidad de que ese nodo tenga${\displaystyle k}$Los vecinos no se dan por${\displaystyle P(k)}$La razón es que, cuando se selecciona algún nodo en una red heterogénea, es más probable que llegue a los hubs siguiendo a uno de los vecinos existentes de ese nodo. La verdadera probabilidad de que tales nodos tengan grado${\displaystyle k}$es${\displaystyle q(k)}$que se denomina grado de exceso de ese nodo. En el modelo de configuración , en el que se han ignorado las correlaciones entre los nodos y se supone que cada nodo está conectado a cualquier otro nodo de la red con la misma probabilidad, la distribución del grado de exceso se puede encontrar como: ^{[ 5 ]}

${\displaystyle q(k)={\frac {k+1}{\langle k\rangle }}P(k+1),}$

dónde${\displaystyle {\langle k\rangle }}$es el grado medio (grado promedio) del modelo. De ello se deduce que el grado promedio del vecino de cualquier nodo es mayor que el grado promedio de ese nodo. En redes sociales, esto significa que tus amigos, en promedio, tienen más amigos que tú. Esto se conoce como la paradoja de la amistad . Se puede demostrar que una red puede tener un componente gigante si su grado promedio en exceso es mayor que uno.

${\displaystyle \sum _{k}kq(k)>1\Rightarrow {\langle k^{2}\rangle }/{\langle k\rangle }-1>1\Rightarrow {\langle k^{2}\rangle }-2{\langle k\rangle }>0}$

Tenga en cuenta que las dos últimas ecuaciones son solo para el modelo de configuración y para derivar la distribución de grado en exceso de una red del mundo real, también debemos agregar correlaciones de grado. ^{[ 5 ]}

Las funciones generadoras se pueden utilizar para calcular diferentes propiedades de redes aleatorias. Dada la distribución de grados y la distribución de grados excedentes de alguna red,${\displaystyle P(k)}$y${\displaystyle q(k)}$respectivamente, es posible escribir dos series de potencias de las siguientes formas:

${\displaystyle G_{0}(x)=\textstyle \sum _ {k}\displaystyle P(k)x^{k}}$y${\displaystyle G_{1}(x)=\textstyle \sum _ {k}\displaystyle q(k)x^{k}=\textstyle \sum _ {k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}}$

${\displaystyle G_{1}(x)}$también se puede obtener a partir de derivados de${\displaystyle G_{0}(x)}$:

${\displaystyle G_{1}(x)={\frac {G'_{0}(x)}{G'_{0}(1)}}}$

Si conocemos la función generadora de una distribución de probabilidad${\displaystyle P(k)}$entonces podemos recuperar los valores de${\displaystyle P(k)}$diferenciando:

${\displaystyle P(k)={\frac {1}{k!}}{\operatorname {d} ^{k}\!G \over \operatorname {d} \!x^{k}}{\biggl \vert }_{x=0}}$

Algunas propiedades, por ejemplo los momentos, se pueden calcular fácilmente a partir de${\displaystyle G_{0}(x)}$y sus derivados:

• ${\displaystyle {\langle k\rangle }=G'_{0}(1)}$
• ${\displaystyle {\langle k^{2}\rangle }=G''_{0}(1)+G'_{0}(1)}$

Y en general: ^{[ 5 ]}

• ${\displaystyle {\langle k^{m}\rangle }={\Biggl [}{{\bigg (}\operatorname {x} {\operatorname {d} \! \over \operatorname {dx} \!}{\biggl )}^{m}}G_{0}(x){\Biggl ]}_{x=1}}$

Para redes aleatorias con distribución de Poisson , como el grafo ER ,${\displaystyle G_{1}(x)=G_{0}(x)}$, esa es la razón por la que la teoría de redes aleatorias de este tipo es especialmente simple. Las distribuciones de probabilidad para los vecinos más cercanos (1.º y 2.º) se generan mediante las funciones${\displaystyle G_{0}(x)}$y${\displaystyle G_{0}(G_{1}(x))}$. Por extensión, la distribución de${\displaystyle m}$-el vecino -ésimo se genera mediante:

${\displaystyle G_{0}{\bigl (}G_{1}(...G_{1}(x)...){\bigr )}}$, con${\displaystyle m-1}$iteraciones de la función${\displaystyle G_{1}}$actuando sobre sí mismo. ^{[ 6 ]}

El número promedio de primeros vecinos,${\displaystyle c_{1}}$, es${\displaystyle {\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}}$y el número promedio de segundos vecinos es:${\displaystyle c_{2}={\biggl [}{d \over dx}G_{0}{\big (}G_{1}(x){\big )}{\biggl ]}_{x=1}=G_{1}'(1)G'_{0}{\big (}G_{1}(1){\big )}=G_{1}'(1)G'_{0}(1)=G''_{0}(1)}$

En una red dirigida, cada nodo tiene un cierto grado de entrada.${\displaystyle k_{in}}$y algunos grados superiores${\displaystyle k_{out}}$que son el número de enlaces que han entrado y salido de ese nodo respectivamente. Si${\displaystyle P(k_{in},k_{out})}$es la probabilidad de que un nodo elegido al azar tenga grado de entrada${\displaystyle k_{in}}$y grado de salida${\displaystyle k_{out}}$entonces la función generadora asignada a esta distribución de probabilidad conjunta se puede escribir con dos valores${\displaystyle x}$y${\displaystyle y}$como:

${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}.}$

Dado que cada enlace en una red dirigida debe salir de algún nodo y entrar en otro, el número promedio neto de enlaces que entran en un nodo es cero. Por lo tanto,

${\displaystyle \langle {k_{in}-k_{out}}\rangle =\sum _{k_{in},k_{out}}\displaystyle (k_{in}-k_{out})P({k_{in},k_{out}})=0}$,

lo que implica que la función de generación debe satisfacer:

${\displaystyle {\partial {\mathcal {G}} \over \partial x}\vert _{x,y=1}={\partial {\mathcal {G}} \over \partial y}\vert _{x,y=1}=c,}$

dónde${\displaystyle c}$es el grado medio (tanto de entrada como de salida) de los nodos en la red;${\displaystyle \langle {k_{in}}\rangle =\langle {k_{out}}\rangle =c.}$

Usando la función${\displaystyle {\mathcal {G}}(x,y)}$, podemos encontrar nuevamente la función de generación para la distribución de grado de entrada/salida y la distribución de grado de exceso de entrada/salida, como antes.${\displaystyle G_{0}^{in}(x)}$se pueden definir como funciones generadoras para el número de enlaces que llegan a un nodo elegido al azar, y${\displaystyle G_{1}^{in}(x)}$Se puede definir como el número de enlaces que llegan a un nodo al que se llega siguiendo un enlace elegido al azar. También podemos definir funciones generadoras.${\displaystyle G_{0}^{out}(y)}$y${\displaystyle G_{1}^{out}(y)}$para el número que sale de dicho nodo: ^{[ 6 ]}

• ${\displaystyle G_{0}^{in}(x)={\mathcal {G}}(x,1)}$
• ${\displaystyle G_{1}^{in}(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$
• ${\displaystyle G_{0}^{out}(y)={\mathcal {G}}(1,y)}$
• ${\displaystyle G_{1}^{out}(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

Aquí, el número promedio de primeros vecinos,${\displaystyle c}$, o como se presentó anteriormente como${\displaystyle c_{1}}$, es${\displaystyle {\partial {\mathcal {G}} \over \partial x}{\biggl \vert }_{x,y=1}={\partial {\mathcal {G}} \over \partial y}{\biggl \vert }_{x,y=1}}$y el número promedio de segundos vecinos alcanzables desde un nodo elegido al azar viene dado por:${\displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={\partial ^{2}{\mathcal {G}} \over \partial x\partial y}{\biggl \vert }_{x,y=1}}$. Estos son también los números de vecinos de primer y segundo orden desde los que se puede llegar a un nodo aleatorio, ya que estas ecuaciones son manifiestamente simétricas en${\displaystyle x}$y${\displaystyle y}$. ^{[ 6 ]}

En una red con signos, cada nodo tiene un grado positivo.${\displaystyle k_{+}}$y un grado negativo${\displaystyle k_{-}}$que son el número positivo de enlaces y el número negativo de enlaces conectados a ese nodo respectivamente. Entonces${\displaystyle P(k_{+})}$y${\displaystyle P(k_{-})}$denotan la distribución de grado negativa y la distribución de grado positiva de la red con signos. ^{[ 7 ] [ 8 ]}

• teoría de grafos
• Red compleja
• Red libre de escala
• Grafo aleatorio
• Corte estructural

• Albert, R.; Barabasi, A.-L. (2002). "Mecánica estadística de redes complejas". Reviews of Modern Physics . 74 (1): 47– 97. arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . S2CID 60545 . 
• Dorogovtsev, S.; Mendes, JFF (2002). "Evolución de las redes". Advances in Physics . 51 (4): 1079– 1187. arXiv : cond-mat/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080/00018730110112519 . S2CID 429546 . 
• Newman, MEJ (2003). "La estructura y función de las redes complejas". SIAM Review . 45 (2): 167– 256. arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137/S003614450342480 . S2CID 221278130 .