Distribución de grados

En el estudio de gráficos 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 aristas que tiene el nodo con otros nodos. Si una red está dirigida , es decir, las aristas apuntan en una dirección desde un nodo a otro, entonces los nodos tienen dos grados diferentes: el grado de entrada, que es la cantidad de aristas entrantes, y el grado de salida, que es la cantidad 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 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 de grado acumulativo ; es decir , el complemento de C.

Distribuciones de grados observadas

La distribución de grados es muy importante en el estudio de redes reales, como Internet y las redes sociales , y 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 independientemente (o no) con 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 se mantiene fijo). Sin embargo, la mayoría de las redes en el mundo real tienen distribuciones de grado muy diferentes de esto. La mayoría están altamente sesgadas a la derecha , lo que significa que una gran mayoría de nodos tienen un grado bajo pero un pequeño número, conocido como "centros", tienen un grado alto. Se argumentó que algunas redes, en particular Internet, la World Wide Web y algunas redes sociales, tienen distribuciones de grado que siguen aproximadamente una ley de potencia : , donde γ es una constante. Dichas redes se denominan redes libres de escala y han atraído particular atención por sus propiedades estructurales y dinámicas. ^{[1] [2] [3] [4]} Sin embargo, un estudio de una amplia gama de redes del mundo real sugiere que las redes libres de escala son raras cuando se evalúan utilizando medidas estadísticamente rigurosas. ^[5] Algunos investigadores han cuestionado estos hallazgos argumentando que las definiciones utilizadas en el estudio son inapropiadamente estrictas, ^[6] mientras que otros han argumentado que la forma funcional precisa de la distribución de grado es menos importante que saber si la distribución de grado es de cola gruesa o no. ^[7] También se ha criticado la interpretación excesiva de formas específicas de la distribución de grados por no tener en cuenta cómo pueden evolucionar las redes con el tiempo. ^[8] ${\displaystyle \langle k\rangle =p(n-1)}$ ${\displaystyle P(k)\sim k^{-\gamma }}$

Distribución de grados en exceso

La distribución de grado excedente es la distribución de probabilidad, para un nodo alcanzado siguiendo una arista, del número de otras aristas unidas a ese nodo. ^[9] En otras palabras, es la distribución de enlaces salientes desde un nodo alcanzado siguiendo un enlace.

Supongamos que una red tiene una distribución de grado , al seleccionar un nodo (al azar o no) y dirigirse a uno de sus vecinos (asumiendo que tiene al menos un vecino), entonces la probabilidad de que ese nodo tenga vecinos no está dada por . La razón es que, siempre que se selecciona un nodo en una red heterogénea, es más probable llegar a los centros siguiendo a uno de los vecinos existentes de ese nodo. La verdadera probabilidad de que dichos nodos tengan grado es lo que se denomina el grado en 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 de grado en exceso se puede encontrar como: ^[9] ${\displaystyle P(k)}$ ${\displaystyle k}$ ${\displaystyle P(k)}$ ${\displaystyle k}$ ${\displaystyle q(k)}$

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

donde es el grado medio (grado promedio) del modelo. De ahí se deduce que el grado promedio del vecino de cualquier nodo es mayor que el grado promedio de ese nodo. En las redes sociales, significa que tus amigos, en promedio, tienen más amigos que tú. Esto es famoso 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 {\langle k\rangle }}$

${\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 tener en cuenta las correlaciones de grado. ^[9]

Método de generación de funciones

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, y respectivamente, es posible escribir dos series de potencias en las siguientes formas: ${\displaystyle P(k)}$ ${\displaystyle q(k)}$

${\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 entonces podemos recuperar los valores de diferenciando: ${\displaystyle P(k)}$ ${\displaystyle P(k)}$

${\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 y sus derivadas: ${\displaystyle G_{0}(x)}$

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

Y en general: ^[9]

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

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

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

El número promedio de primeros vecinos, , es y el número promedio de segundos vecinos es: ${\displaystyle c_{1}}$ ${\displaystyle {\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}}$ ${\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)}$

Distribución de grados para redes dirigidas

Distribución de grados de entrada y salida para el gráfico de hipervínculos de Wikipedia (escalas logarítmicas)

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

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

Como cada enlace de una red dirigida debe salir de un nodo y entrar en otro, el número neto promedio 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,}$

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

Utilizando la función , 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. se pueden definir como funciones generadoras para el número de enlaces que llegan a un nodo elegido aleatoriamente, y se pueden definir como el número de enlaces que llegan a un nodo alcanzado siguiendo un enlace elegido aleatoriamente. También podemos definir funciones generadoras y para el número que sale de dicho nodo: ^[10] ${\displaystyle {\mathcal {G}}(x,y)}$ ${\displaystyle G_{0}^{in}(x)}$ ${\displaystyle G_{1}^{in}(x)}$ ${\displaystyle G_{0}^{out}(y)}$ ${\displaystyle G_{1}^{out}(y)}$

• ${\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, , o como se introdujo anteriormente como , es y el número promedio de segundos vecinos alcanzables desde un nodo elegido aleatoriamente está dado por: . Estos son también los números de primeros y segundos vecinos desde los cuales se puede alcanzar un nodo aleatorio, ya que estas ecuaciones son manifiestamente simétricas en y . ^[10] ${\displaystyle c}$ ${\displaystyle c_{1}}$ ${\displaystyle {\partial {\mathcal {G}} \over \partial x}{\biggl \vert }_{x,y=1}={\partial {\mathcal {G}} \over \partial y}{\biggl \vert }_{x,y=1}}$ ${\displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={\partial ^{2}{\mathcal {G}} \over \partial x\partial y}{\biggl \vert }_{x,y=1}}$ ${\displaystyle x}$ ${\displaystyle y}$

Distribución de grados para redes firmadas

En una red firmada, cada nodo tiene un grado positivo y un grado negativo , que son el número positivo y el número negativo de enlaces conectados a ese nodo respectivamente. Por lo tanto, y denotan la distribución de grado negativo y la distribución de grado positivo de la red firmada. ^{[11] [12]} ${\displaystyle k_{+}}$ ${\displaystyle k_{-}}$ ${\displaystyle P(k_{+})}$ ${\displaystyle P(k_{-})}$

Véase también

• Teoría de grafos
• Red compleja
• Red sin escala
• Gráfico aleatorio
• Corte estructural

Referencias

1. Barabási, Albert-László; Albert, Réka (15 de octubre de 1999). "Aparición del escalamiento en redes aleatorias". Ciencia . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Código Bib : 1999 Ciencia... 286.. 509B. doi : 10.1126/ciencia.286.5439.509. ISSN  0036-8075. PMID  10521342. S2CID  524106.
2. Albert, Réka; Barabási, Albert-László (11 de diciembre de 2000). "Topología de redes en evolución: eventos locales y universalidad" (PDF) . Physical Review Letters . 85 (24): 5234–5237. arXiv : cond-mat/0005085 . Bibcode :2000PhRvL..85.5234A. doi :10.1103/physrevlett.85.5234. hdl :2047/d20000695. ISSN  0031-9007. PMID  11102229. S2CID  81784. Archivado (PDF) desde el original el 21 de julio de 2018 . Consultado el 25 de septiembre de 2019 .
3. Dorogovtsev, SN; Mendes, JFF; Samukhin, AN (21 de mayo de 2001). "Distribución de grados dependiente del tamaño de una red de crecimiento libre de escala". Physical Review E . 63 (6): 062101. arXiv : cond-mat/0011115 . Bibcode :2001PhRvE..63f2101D. doi :10.1103/physreve.63.062101. ISSN  1063-651X. PMID  11415146. S2CID  119063903.
4. Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Comportamiento libre de escala de redes con copresencia de reglas de unión preferencial y uniforme". Physica D: Nonlinear Phenomena . 371 : 1–12. arXiv : 1704.08597 . Bibcode :2018PhyD..371....1P. doi :10.1016/j.physd.2018.01.005. S2CID  119320331.
5. Broido, Anna D.; Clauset, Aaron (4 de marzo de 2019). "Las redes sin escala son raras". Nature Communications . 10 (1): 1017. doi : 10.1038/s41467-019-08746-5 . ISSN  2041-1723. PMC 6399239 . PMID  30833554. 
6. Voitalov, Iván; van der Hoorn, Pim; van der Hofstad, Remco; Krioukov, Dmitri (18 de octubre de 2019). "Redes sin escala bien hechas". Investigación de revisión física . 1 (3): 033034. arXiv : 1811.02071 . doi : 10.1103/PhysRevResearch.1.033034 .
7. Holme, Petter (4 de marzo de 2019). "Raro y omnipresente: Perspectivas sobre redes sin escala". Nature Communications . 10 (1): 1016. Bibcode :2019NatCo..10.1016H. doi :10.1038/s41467-019-09038-8. ISSN  2041-1723. PMC 6399274 . PMID  30833568. 
8. Falkenberg, Max; Lee, Jong-Hyeok; Amano, Shun-ichi; Ogawa, Ken-ichiro; Yano, Kazuo; Miyake, Yoshihiro; Evans, Tim S.; Christensen, Kim (18 de junio de 2020). "Identificación de la dependencia del tiempo en el crecimiento de la red". Physical Review Research . 2 (2): 023352. arXiv : 2001.09118 . doi : 10.1103/PhysRevResearch.2.023352 .
9. Newman, Mark (18 de octubre de 2018). Redes. Vol. 1. Oxford University Press. doi :10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0Archivado desde el original el 15 de abril de 2020. Consultado el 19 de abril de 2020 .
10. Newman, MEJ; Strogatz, SH; Watts, DJ (24 de julio de 2001). "Gráficos aleatorios con distribuciones de grado arbitrario y sus aplicaciones". Physical Review E . 64 (2): 026118. arXiv : cond-mat/0007235 . doi : 10.1103/PhysRevE.64.026118 . ISSN  1063-651X. PMID  11497662.
11. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (enero de 2021). "Impacto topológico de los vínculos negativos en la estabilidad de la red cerebral en estado de reposo". Scientific Reports . 11 (1): 2176. doi :10.1038/s41598-021-81767-7. PMC 7838299 . PMID  33500525. 
12. Ciotti V (2015). "Correlaciones de grado en redes sociales signadas". Physica A: Mecánica estadística y sus aplicaciones . 422 : 25–39. arXiv : 1412.1024 . doi :10.1016/j.physa.2014.11.062. S2CID  4995458. Archivado desde el original el 2021-10-02 . Consultado el 2021-02-10 .

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