Distribución de grados

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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.

Definición

El grado de un nodo en una red (a veces denominado incorrectamente conectividad) es la cantidad de conexiones o bordes que tiene el nodo con otros nodos. Si una red es dirigida, lo que significa que los bordes apuntan en una dirección de un nodo a otro, entonces los nodos tienen dos grados diferentes, el grado de entrada, que es el número de bordes entrantes, y el grado de salida, que es el número de bordes 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. Así 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 acumulativo, la fracción de nodos con grado menor que k, o incluso la distribución de grado acumulativo complementaria, la fracción de nodos con grado mayor o igual a k (1 - C) si se considera C como la distribución acumulada de grados; es decir, el complemento de C.

Distribuciones de grados observadas

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

(o Poisson en el límite de n grande, si el grado medio ${displaystyle langle krangle =p(n-1)}$ se mantiene fijo). Sin embargo, la mayoría de las redes en el mundo real tienen distribuciones de grados muy diferentes a esta. La mayoría tienen un alto sesgo hacia la derecha, lo que significa que la gran mayoría de los nodos tienen un grado bajo, pero un pequeño número, conocido como "hubs", tiene un grado alto. Se argumentó que algunas redes, en particular Internet, la World Wide Web y algunas redes sociales, tienen distribuciones de grados que siguen aproximadamente una ley de potencia: ${ estilo de visualización P(k)simk^{-gamma}}$ , donde γ es una constante. Este tipo de redes se denominan redes libres de escala y han atraído una atención particular por sus propiedades estructurales y dinámicas.Sin embargo, una encuesta de una amplia gama de redes del mundo real sugiere que las redes sin escala son raras cuando se evalúan utilizando medidas estadísticamente rigurosas. Algunos investigadores han cuestionado estos hallazgos argumentando que las definiciones utilizadas en el estudio son inadecuadamente estrictas, mientras que otros han argumentado que la forma funcional precisa de la distribución de grados es menos importante que saber si la distribución de grados es de cola gruesa o no. También se ha criticado la sobreinterpretación de formas específicas de distribución de grados por no tener en cuenta cómo pueden evolucionar las redes con el tiempo.

Distribución de exceso de titulación

La distribución de exceso de grado es la distribución de probabilidad, para un nodo alcanzado siguiendo un borde, del número de otros bordes conectados a ese nodo. En otras palabras, es la distribución de enlaces salientes desde un nodo al que se llega siguiendo un enlace.

Supongamos que una red tiene una distribución de grados ${ estilo de visualización P (k)}$ , seleccionando un nodo (al azar o no) y yendo a uno de sus vecinos (suponiendo que tenga al menos un vecino), entonces la probabilidad de que ese nodo tenga ${ estilo de visualización k}$ vecinos no está dada por ${ estilo de visualización P (k)}$ . La razón es que, siempre que se seleccione algún nodo en una red heterogénea, es más probable llegar a los hubs siguiendo a uno de los vecinos existentes de ese nodo. La verdadera probabilidad de que tales nodos tengan grado ${ estilo de visualización k}$ es ${ estilo de visualización q (k)}$ lo que se denomina exceso de grado de ese nodo. En el modelo de configuración, cuyas correlaciones entre los nodos se han ignorado y se supone que cada nodo está conectado a cualquier otro nodo de la red con la misma probabilidad, la distribución de exceso de grado se puede encontrar como:

{displaystyle q(k)={frac {k+1}{langle krangle }}P(k+1),}

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

{displaystyle sum_{k}kq(k)>1Rightarrow {langle k^{2}rangle}/{langle krangle}-1>1Rightarrow {langle k^{2} rangle }-2{langle krangle }>0}

Tenga en cuenta que las dos últimas ecuaciones son solo para el modelo de configuración y para derivar la distribución de grados en exceso de una red real, también debemos tener en cuenta las correlaciones de grados.

El método de funciones generadoras

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 en exceso de alguna red, ${ estilo de visualización P (k)}$ y ${ estilo de visualización q (k)}$ respectivamente, es posible escribir dos series de potencias en 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}}$

${ estilo de visualización G_ {1} (x)}$ también se puede obtener a partir de derivados de ${ estilo de visualización 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, ${ estilo de visualización P (k)}$ entonces podemos recuperar los valores de ${ estilo de visualización P (k)}$ derivando:

{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 ${ estilo de visualización G_ {0} (x)}$ sus derivadas:

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

Y en general:

${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 gráfico ER ${displaystyle G_{1}(x)=G_{0}(x)}$ , esa es la razón por la cual la teoría de redes aleatorias de este tipo es especialmente simple. Las distribuciones de probabilidad para el primer y segundo vecino más cercano son generadas por las funciones ${ estilo de visualización G_ {0} (x)}$ y ${displaystyle G_{0}(G_{1}(x))}$ . Por extensión, la distribución de ${ estilo de visualización m}$ vecinos -ésimos se genera mediante:

${displaystyle G_{0}{bigl (}G_{1}(...G_{1}(x)...){bigr)}}$ , con ${ estilo de visualización m-1}$ iteraciones de la función ${ estilo de visualización G_ {1}}$ actuando sobre sí misma.

El número promedio de primeros vecinos, ${ estilo de visualización c_ {1}}$ , es ${displaystyle {langle krangle }={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}{grande (}G_{1}(1){grande)}=G_{1}'(1)G'_{0}(1)=G''_{0}(1)}$

Distribución de grados para redes dirigidas

En una red dirigida, cada nodo tiene un grado de entrada ${displaystyle k_{en}}$ y un grado de salida, ${displaystyle k_{fuera}}$ que son el número de enlaces que entran y salen de ese nodo respectivamente. Si ${displaystyle P(k_{entrada},k_{salida})}$ es la probabilidad de que un nodo elegido al azar tenga grado de ${displaystyle k_{en}}$ entrada y salida, ${displaystyle k_{fuera}}$ entonces la función generadora asignada a esta distribución de probabilidad conjunta se puede escribir con dos valores ${ estilo de visualización x}$ y ${ estilo de visualización y}$ como:

{displaystyle {mathcal {G}}(x,y)=sum_{k_{entrada},k_{salida}}displaystyle P({k_{entrada},k_{salida}})x^{k_ {entrada}}y^{k_{salida}}.}

Dado que cada enlace en una red dirigida debe salir de algún nodo y entrar en otro, el número medio 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_ {entrada},k_{salida}})=0}$ ,

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

{displaystyle {parcial {mathcal {G}} over parcial x}vert _{x,y=1}={parcial {mathcal {G}} over parcial y}vert _{ x,y=1}=c,}

donde ${ estilo de visualización 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 grados de entrada/salida y la distribución de grados de entrada/salida, como antes. ${displaystyle G_{0}^{en}(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}^{en}(x)}$ se pueden 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}^{fuera}(y)}$ y ${displaystyle G_{1}^{fuera}(y)}$ para el número que sale de tal nodo:

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

Aquí, el número promedio de primeros vecinos, ${ estilo de visualización c}$ , o como se introdujo anteriormente como ${ estilo de visualización c_ {1}}$ , es ${displaystyle {parcial {mathcal {G}} over parcial x}{biggl vert }_{x,y=1}={parcial {mathcal {G}} over parcial y} {bigglvert}_{x,y=1}}$ y el número promedio de segundos vecinos accesibles desde un nodo elegido al azar viene dado por: ${displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={parcial ^{2}{mathcal {G}} sobre parcial xparcial y}{ bigglvert}_{x,y=1}}$ . Estos son también los números de vecinos 1 y 2 a partir de los cuales se puede llegar a un nodo aleatorio, ya que estas ecuaciones son manifiestamente simétricas en ${ estilo de visualización x}$ y ${ estilo de visualización y}$ .

Distribución de grados para redes firmadas

En una red firmada, 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 PAG(k_{+})}$ y ${displaystyle PAG(k_{-})}$ denote la distribución de grado negativo y la distribución de grado positivo de la red firmada.

Contenido relacionado

Más resultados...