Red escasa

En ciencia de redes , una red dispersa tiene muchos menos enlaces que el número máximo posible de enlaces dentro de esa red (lo contrario es una red densa ). El estudio de redes dispersas es un área relativamente nueva estimulada principalmente por el estudio de redes reales, como las redes sociales y de computadoras. ^[1]

La noción de muchos menos vínculos es, por supuesto, coloquial e informal. Si bien se puede inventar un umbral para una red particular, no existe un umbral universal que defina lo que realmente significa mucho menos . Como resultado, no existe una sensación formal de escasez para ninguna red finita, a pesar del acuerdo generalizado de que la mayoría de las redes empíricas son efectivamente escasas. Sin embargo, existe una sensación formal de escasez en el caso de modelos de redes infinitas, determinada por el comportamiento del número de aristas (M) y/o el grado promedio ( ⟨k⟩ ) a medida que aumenta el número de nodos (N). hasta el infinito. ^[2]

Definiciones

Una red simple de tamaño no ponderado se denomina dispersa si el número de enlaces que contiene es mucho menor que el número máximo posible de enlaces : ^[1] ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle M_{max}}$

${\displaystyle M\ll M_{max}={N \choose 2}}$.

En cualquier red (real), el número de nodos N y enlaces M son solo dos números, por lo tanto, el significado del signo mucho más pequeño ( arriba) es puramente coloquial e informal, al igual que declaraciones como "muchas redes reales son escasas". " ${\displaystyle \ll }$

Sin embargo, si tratamos con una secuencia gráfica sintética , o un modelo de red que esté bien definido para redes de cualquier tamaño N = 1,2,... ,, entonces adquiere su significado formal habitual: ${\displaystyle G_{N}}$ ${\displaystyle G_{N}}$ ${\displaystyle \infty }$ ${\displaystyle \ll }$

${\displaystyle M\ll M_{max}\iff M=o(M_{max})\iff \lim _{N\rightarrow \infty }{\frac {M}{M_{max}}}=0}$.

En otras palabras, una secuencia o modelo de red se denomina denso o escaso dependiendo de si el grado promedio (esperado) escala lineal o sublinealmente con N : ^[2] [ ^3] ${\displaystyle G_{N}}$ ${\displaystyle \langle k\rangle =2M/N}$ ${\displaystyle G_{N}}$

${\displaystyle G_{N}}$ es denso si ; ${\displaystyle \langle k\rangle =O(N)}$

${\displaystyle G_{N}}$ es escaso si . ${\displaystyle \langle k\rangle =o(N)}$

Una subclase importante de redes dispersas son las redes cuyo grado promedio es constante o converge a una constante. Algunos autores consideran que estas redes son escasas, mientras que otros les reservan nombres especiales: ^[4]

${\displaystyle G_{N}}$ es verdaderamente escaso o extremadamente escaso o ultraescaso si . ${\displaystyle \langle k\rangle =O(1)}$

También existen definiciones alternativas y más estrictas de dispersión de la red que requieren la convergencia de la distribución de grados en un límite bien definido en . ^[5] Según esta definición, el gráfico de N estrellas , por ejemplo, no es escaso. ${\displaystyle G_{N}}$ ${\displaystyle N\rightarrow \infty }$ ${\displaystyle S_{N}}$

Distribución de grados de nodo

La distribución del grado de los nodos cambia con la creciente conectividad. Las diferentes densidades de enlaces en las redes complejas tienen diferentes distribuciones de grados de nodo, como sugiere Flickr Network Analysis. ^[6] Las redes escasamente conectadas tienen una distribución de ley de potencia libre de escala . A medida que aumenta la conectividad, las redes muestran una divergencia cada vez mayor con respecto a la ley de potencia. Uno de los principales factores que influye en la conectividad de la red es la similitud de los nodos . Por ejemplo, en las redes sociales , es probable que las personas estén vinculadas entre sí si comparten antecedentes sociales, intereses, gustos, creencias, etc. en común. En el contexto de las redes biológicas, las proteínas u otras moléculas están vinculadas si tienen un ajuste exacto o complementario. de sus complejas superficies. ^[6]

Terminología común

Si los nodos de las redes no están ponderados, los componentes estructurales de la red se pueden mostrar mediante una matriz de adyacencia . Si la mayoría de los elementos de la matriz son cero, dicha matriz se denomina matriz dispersa . Por el contrario, si la mayoría de los elementos son distintos de cero, entonces la matriz es densa . La escasez o densidad de la matriz se identifica por la fracción del elemento cero respecto al número total de elementos de la matriz. De manera similar, en el contexto de la teoría de grafos , si el número de enlaces está cerca de su máximo, entonces el gráfico se conocería como gráfico denso . Si el número de enlaces es inferior al número máximo de enlaces, este tipo de gráficos se denomina gráfico disperso . ^[7]

Aplicaciones

Sparse Network se puede encontrar en redes sociales , informáticas y biológicas , así como sus aplicaciones se pueden encontrar en transporte , líneas eléctricas, redes de citas, etc. Dado que la mayoría de las redes reales son grandes y dispersas, se desarrollaron varios modelos para comprender y analizarlos. ^[8] Estas redes han inspirado el diseño disperso de redes en chips en la ingeniería informática integrada en multiprocesadores .

Las redes dispersas también inducen cálculos más baratos al hacer eficiente el almacenamiento de la red como una lista de Adyacencia , en lugar de una matriz de Adyacencia . Por ejemplo, cuando se utiliza una lista de adyacencia, la iteración sobre los vecinos de un nodo se puede lograr en O(M/N), mientras que se logra en O(N) con una matriz de adyacencia. ^[2]

Referencias

1. Barabási, Albert-László (2015). Ciencia de redes. Prensa de la Universidad de Cambridge . Consultado el 25 de mayo de 2015 .
2. Newman, Mark. Redes 2ª Edición . Consultado el 14 de febrero de 2021 .
3. Bollobás, Béla (1985). Gráficos aleatorios . Prensa académica.
4. Janson, Svante (2018). "Gráficos aleatorios intercambiables en el borde". J Stat Phys . 173 (3–4): 448–484. arXiv : 1702.06396 . Código Bib : 2018JSP...173..448J. doi :10.1007/s10955-017-1832-9. PMC 6405020 . PMID  30930480. 
5. van der Hofstad, Remco (2017). Gráficos aleatorios y redes complejas . Prensa de la Universidad de Cambridge. doi :10.1017/9781316779422. ISBN 9781316779422.
6. Scholz, Matthias (7 de enero de 2015). "La similitud de nodos como principio básico detrás de la conectividad en redes complejas". Revista de Minería de Datos y Humanidades Digitales . 2015 (77). arXiv : 1010.0803 . doi : 10.46298/jdmdh.33 . S2CID  221799 . Consultado el 25 de mayo de 2015 .
7. Nykamp, ​​Duane Q. "Una introducción a las redes". Perspectiva matemática . Consultado el 25 de mayo de 2015 .
8. Gribonval, Rémi. "Modelos dispersos, algoritmos y aprendizaje para datos a gran escala". PEQUEÑO . Consultado el 25 de mayo de 2015 .