Distribución de títulos - Degree distribution

Ciencia de la red
Teoría
Grafico Red compleja Contagio Mundo pequeño Sin escamas Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de redes
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neural artificial Interdependiente Semántico Espacial Dependencia Flujo en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Círculo Vecindario Camino Vértice Lista  / matriz de adyacencia Lista  / matriz de incidencia Tipos Bipartito Completo Dirigido Hiper Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad La licenciatura Motivo Agrupación Distribución de titulaciones Assortividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős – Rényi Barabási – Albert Modelo de fitness Watts – Strogatz Aleatorio exponencial (ERGM) Geométrico aleatorio (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Entropía máxima Configuración suave Benchmark LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorias
Temas Software Científicos de la red Categoría: Teoría de redes Categoría: Teoría de grafos
v t mi

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 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 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 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 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 \ elige k} p ^ {k} (1-p) ^ {n-1-k},}$

(o Poisson en el límite de n grande , si el grado promedio se 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. 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 inapropiadamente 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 ancha o no. 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. ${\ Displaystyle \ langle k \ rangle = p (n-1)}$${\ Displaystyle P (k) \ sim k ^ {- \ gamma}}$

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. 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 (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 viene 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 en 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: ${\ 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 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: ${\ Displaystyle {\ langle k \ rangle}}$

${\ Displaystyle \ sum _ {k} kq (k)> 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 de palabras reales, también debemos tener en cuenta las correlaciones de grados.

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 potencia 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 , 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 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:

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

Para Poisson -distribuida redes aleatorias, tales como el gráfico de ER , , que es la razón por qué la teoría de redes al azar de este tipo es especialmente simple. Las distribuciones de probabilidad para el primer y segundo vecinos más cercanos son generadas por las funciones y . Por extensión, la distribución de -ésimo vecinos es generada 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. ${\ Displaystyle m-1}$${\ Displaystyle G_ {1}}$

El número medio de primeros vecinos,, es y el número medio 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 titulaciones 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 algún grado de entrada y algún grado de salida, que son 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 de entrada y otro de salida, entonces la función generadora asignada a esta distribución de probabilidad conjunta se puede escribir con dos objetos de valor y como: ${\ displaystyle k_ {in}}$${\ displaystyle k_ {out}}$${\ Displaystyle P (k_ {dentro}, k_ {fuera})}$${\ 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 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_ {in}, k_ {out}}) = 0}$ ,

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

${\ Displaystyle {\ parcial {\ mathcal {G}} \ sobre \ parcial x} \ vert _ {x, y = 1} = {\ parcial {\ mathcal {G}} \ sobre \ parcial y} \ vert _ { x, y = 1} = c,}$

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

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: ${\ 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 \ parcial y} \ vert _ {x = 1}}$

Aquí, el número medio de la 1ª vecinos, o como introducido previamente como , es y el número promedio de la 2ª vecinos accesible desde un nodo elegido al azar está dada 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 . ${\ Displaystyle c}$${\ Displaystyle c_ {1}}$${\ Displaystyle {\ parcial {\ mathcal {G}} \ sobre \ parcial x} {\ biggl \ vert} _ {x, y = 1} = {\ parcial {\ mathcal {G}} \ sobre \ parcial y} {\ biggl \ vert} _ {x, y = 1}}$${\ Displaystyle c_ {2} = G_ {1} '(1) G' _ {0} (1) = {\ parcial ^ {2} {\ mathcal {G}} \ sobre \ parcial x \ parcial y} { \ biggl \ vert} _ {x, y = 1}}$${\ Displaystyle x}$${\ Displaystyle y}$

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. Así y denotan distribución de grados negativos y distribución de grados positivos de la red firmada. ${\ 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

• 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.