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 como conectividad ) es el número de conexiones o bordes que el nodo tiene con otros nodos. Si una red está dirigida , lo que significa que los bordes apuntan en una dirección de un nodo a otro nodo, 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 . Por lo tanto, si hay n nodos en total en una red y n k de ellos tienen grado k , tenemos.
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 un grado menor que k , o incluso la distribución complementaria de grado acumulativo , la fracción de nodos con un grado mayor o igual que k (1 - C ) si se considera C como la distribución acumulativa de grados ; 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 redes sociales , como 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 n nodos está conectado independientemente (o no) con probabilidad p (o 1 - p ), tiene una distribución binomial de grados k :
(o Poisson en el límite de n grande , si el grado mediose mantiene fijo). La mayoría de las redes en el mundo real, sin embargo, 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 número pequeño, conocido como "concentradores", 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 :, donde γ es una constante. Estas redes se denominan redes sin escala y han atraído una atención especial 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 es de cola ancha. o no. [7] La sobreinterpretación de formas específicas de distribución de títulos también ha sido criticada por no considerar cómo las redes pueden evolucionar con el tiempo. [8]
Exceso de distribución de títulos
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 adjuntos a ese nodo. [9] En otras palabras, es la distribución de enlaces salientes desde un nodo al que se llega siguiendo un enlace.
Suponga que una red tiene una distribución de grados , 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 vecinos no se da 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 tales nodos tengan grado es que se llama el grado de exceso 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 grados en exceso se puede encontrar como: [9]
dónde es el grado medio (grado medio) del modelo. De ello se desprende 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 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:
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 de palabras reales, también debemos tener en cuenta las correlaciones de grados. [9]
El 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 en las siguientes formas:
y
también se puede obtener a partir de derivados de :
Si conocemos la función generadora de una distribución de probabilidad entonces podemos recuperar los valores de diferenciando:
Algunas propiedades, por ejemplo, los momentos, se pueden calcular fácilmente a partir de y sus derivados:
Y en general: [9]
Para redes aleatorias distribuidas por Poisson , como el gráfico ER ,, por eso la teoría de las redes aleatorias de este tipo es especialmente sencilla. 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-th vecinos es generado por:
, con iteraciones de la función actuando sobre sí mismo. [10]
El número medio de primeros vecinos, , es y el número promedio de segundos vecinos es:
Distribución de titulaciones para redes dirigidas
En una red dirigida, cada nodo tiene cierto grado y un poco de grado cuál es el número de enlaces que han entrado y salido de ese nodo respetuosamente. Si es la probabilidad de que un nodo elegido al azar tenga un grado y fuera de grado entonces la función generadora asignada a esta distribución de probabilidad conjunta se puede escribir con dos objetos de valor y como:
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,
,
lo que implica que la función de generación debe satisfacer:
dónde es el grado medio (tanto de entrada como de salida) de los nodos de la red;
Usando la función , 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. 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]
Aquí, el número promedio de primeros vecinos, , o como se introdujo previamente 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 del primer y segundo vecinos desde los que se puede llegar a un nodo aleatorio, ya que estas ecuaciones son manifiestamente simétricas en y . [10]
Distribución de titulaciones 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 respetuosamente. Entonces y denotan distribución de grados negativos y distribución de grados positivos de la red firmada. [11] [12]
Ver también
Referencias
- ^ Barabási, Albert-László; Albert, Réka (15 de octubre de 1999). "Aparición del escalado en redes aleatorias". Ciencia . 286 (5439): 509–512. arXiv : cond-mat / 9910332 . Código Bibliográfico : 1999Sci ... 286..509B . doi : 10.1126 / science.286.5439.509 . ISSN 0036-8075 . PMID 10521342 .
- ^ 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) . Cartas de revisión física . 85 (24): 5234–5237. arXiv : cond-mat / 0005085 . Código Bibliográfico : 2000PhRvL..85.5234A . doi : 10.1103 / physrevlett.85.5234 . hdl : 2047 / d20000695 . ISSN 0031-9007 . PMID 11102229 .
- ^ Dorogovtsev, SN; Mendes, JFF; Samukhin, AN (21 de mayo de 2001). "Distribución de grados en función del tamaño de una red en crecimiento sin escala". Revisión E física . 63 (6): 062101. arXiv : cond-mat / 0011115 . Código Bibliográfico : 2001PhRvE..63f2101D . doi : 10.1103 / physreve.63.062101 . ISSN 1063-651X . PMID 11415146 .
- ^ Pachón, Angélica; Sacerdote, Laura; Yang, Shuyi (2018). "Comportamiento libre de escala de las redes con la copresencia de reglas de apego preferenciales y uniformes". Physica D: Fenómenos no lineales . 371 : 1-12. arXiv : 1704.08597 . Código bibliográfico : 2018PhyD..371 .... 1P . doi : 10.1016 / j.physd.2018.01.005 .
- ^ 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 .
- ^ Voitalov, Ivan; van der Hoorn, Pim; van der Hofstad, Remco; Krioukov, Dmitri (18 de octubre de 2019). "Redes libres de escala bien hechas" . Investigación de revisión física . 1 (3): 033034. doi : 10.1103 / PhysRevResearch.1.033034 .
- ^ Holme, Petter (4 de marzo de 2019). "Raro y en todas partes: perspectivas sobre redes sin escala" . Comunicaciones de la naturaleza . 10 (1): 1016. Bibcode : 2019NatCo..10.1016H . doi : 10.1038 / s41467-019-09038-8 . ISSN 2041-1723 . PMC 6399274 . PMID 30833568 .
- ^ 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" . Investigación de revisión física . 2 (2): 023352. doi : 10.1103 / PhysRevResearch.2.023352 .
- ^ a b c d Newman, Mark (18 de octubre de 2018). Redes . 1 . Prensa de la Universidad de Oxford. doi : 10.1093 / oso / 9780198805090.001.0001 . ISBN 978-0-19-880509-0.
- ^ a b c Newman, MEJ; Strogatz, SH; Watts, DJ (24 de julio de 2001). "Gráficos aleatorios con distribuciones de grados arbitrarias y sus aplicaciones" . Revisión E física . 64 (2): 026118. doi : 10.1103 / PhysRevE.64.026118 . ISSN 1063-651X .
- ^ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (enero de 2021). "Impacto topológico de los enlaces negativos sobre la estabilidad de la red del cerebro en estado de reposo" . Informes científicos . doi : 10.1038 / s41598-021-81767-7 . PMC 7838299 . PMID 33500525 .
- ^ Ciotti V (2015). "Correlaciones de grado en redes sociales firmadas" . Physica A: Mecánica estadística y sus aplicaciones . arXiv : 1412.1024 . doi : 10.1016 / j.physa.2014.11.062 .
- 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 .
- 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 .
- Newman, MEJ (2003). "La estructura y función de redes complejas". Revisión SIAM . 45 (2): 167–256. arXiv : cond-mat / 0303516 . Código bibliográfico : 2003SIAMR..45..167N . doi : 10.1137 / S003614450342480 .
- Shlomo Havlin y Reuven Cohen (2010). Redes complejas: estructura, robustez y función . Prensa de la Universidad de Cambridge.