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 el número de conexiones o aristas que tiene el nodo con otros nodos. Si una red está 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 los 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 a veces también se presenta en forma de distribución de grados acumulativos , la fracción de nodos con grados menores que k , o incluso la distribución de grados acumulativos complementaria , la fracción de nodos con grados mayores o iguales a k (1 - C ) si se considera C como la distribución de grados acumulada ; es decir, el complemento de C .

Distribuciones de grados observadas

La distribución de títulos es muy importante en el estudio tanto de redes reales, como Internet y las redes sociales , como de 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) independientemente 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 del mundo real tienen distribuciones de grados muy diferentes a esta. La mayoría están muy sesgados 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 "hubs", tiene un grado alto. Se argumentó que algunas redes, en particular Internet, la World Wide Web y algunas redes sociales, tenían distribuciones de grados que siguen aproximadamente una ley de potencia : , donde γ es una constante. Estas redes se denominan redes sin escala y han atraído especial atención por sus propiedades estructurales y dinámicas. ^{[1] [2] [3] [4]} 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. ^[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 grados es menos importante que saber si la distribución de grados tiene} cola gruesa . O no. ^[7] La ​​sobreinterpretación de formas específicas de la distribución de títulos también ha sido criticada por no considerar cómo las redes pueden evolucionar con el tiempo. ^[8] ${\displaystyle \langle k\rangle =p(n-1)}$ ${\displaystyle P(k)\sim k^{-\gamma }}$

Distribución excesiva de grados

La distribución de grados en exceso es la distribución de probabilidad, para un nodo alcanzado siguiendo un borde, del número de otros bordes unidos a ese nodo. ^[9] 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 , 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 vecinos no está dada por . La razón es que, siempre que se selecciona 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 dichos nodos tengan grado es lo que se denomina grado excesivo de ese nodo. En el modelo de configuración , en el que se ignoran 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 grados 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 ello 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 se conoce como la paradoja de la amistad . Se puede demostrar que una red puede tener una 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 grados en exceso de una red real, también debemos tener en cuenta las correlaciones de grados. ^[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 en exceso de alguna red, y respectivamente, es posible escribir dos series de potencias de 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 derivando: ${\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 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}}$

Para las redes aleatorias distribuidas por Poisson , como el gráfico ER , 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 y . Por extensión, la distribución de -ésimos vecinos se genera por: ${\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/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 el número de enlaces que han entrado y salido de ese nodo respectivamente. Si es la probabilidad de que un nodo elegido al azar tenga grados de entrada y 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}}.}$

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 ingresan a 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 está 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.}$

Usando la función , podemos nuevamente encontrar la función de generación para la distribución de grados de entrada/salida y la distribución de grados de exceso de entrada/fuera, como antes. se puede definir como funciones generadoras para el número de enlaces que llegan a un nodo elegido al azar, y 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 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 accesibles desde un nodo elegido al azar viene dado por :. Estos son también los números de los vecinos primero y segundo desde los cuales se puede llegar a 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 de enlaces y el número negativo de enlaces conectados a ese nodo respectivamente. Entonces y denota una distribución de grados negativos y una distribución de grados positivos de la red con signo. ^{[11] [12]} ${\displaystyle k_{+}}$ ${\displaystyle k_{-}}$ ${\displaystyle P(k_{+})}$ ${\displaystyle P(k_{-})}$

Ver 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. Alberto, Réka; Barabási, Albert-László (11 de diciembre de 2000). "Topología de redes en evolución: eventos locales y universalidad" (PDF) . Cartas de revisión física . 85 (24): 5234–5237. arXiv : cond-mat/0005085 . Código Bib : 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 en crecimiento sin escala". Revisión física E. 63 (6): 062101. arXiv : cond-mat/0011115 . Código bibliográfico : 2001PhRvE..63f2101D. doi :10.1103/physreve.63.062101. ISSN  1063-651X. PMID  11415146. S2CID  119063903.
4. Pachón, Angélica; Sacerdote, Laura; Yang, Shuyi (2018). "Comportamiento de redes sin escala con la copresencia de reglas de vinculación preferenciales y uniformes". Physica D: Fenómenos no lineales . 371 : 1–12. arXiv : 1704.08597 . Código Bib : 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". Comunicaciones de la naturaleza . 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). "Raros y en todas partes: perspectivas sobre redes sin escala". Comunicaciones de la naturaleza . 10 (1): 1016. Código bibliográfico : 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). "Identificar la dependencia del tiempo en el crecimiento de la red". Investigación de revisión física . 2 (2): 023352. arXiv : 2001.09118 . doi : 10.1103/PhysRevResearch.2.023352 .
9. Newman, Mark (18 de octubre de 2018). Redes. vol. 1. Prensa de la Universidad de Oxford. doi :10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0. Archivado 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 grados arbitrarios y sus aplicaciones". Revisión física 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 enlaces negativos en la estabilidad de la red cerebral en estado de reposo". Informes científicos . 11 (1): 2176. doi : 10.1038/s41598-021-81767-7. PMC 7838299 . PMID  33500525. 
12. Ciotti V (2015). "Correlaciones de grados en redes sociales firmadas". 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 2 de octubre de 2021 . Consultado el 10 de febrero de 2021 .

• Alberto, 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 Bib : 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 Bib : 2002AdPhy..51.1079D. doi :10.1080/00018730110112519. S2CID  429546.
• Newman, MEJ (2003). "La estructura y función de redes complejas". Revisión SIAM . 45 (2): 167–256. arXiv : cond-mat/0303516 . Código Bib : 2003SIAMR..45..167N. doi :10.1137/S003614450342480. S2CID  221278130.