Red dispersa

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

La noción de muchos menos enlaces es, por supuesto, coloquial e informal. Si bien se puede inventar un umbral para una red particular, no existe un umbral universal que defina qué significa realmente " muchos menos" . En consecuencia, no existe un concepto formal de escasez para ninguna red finita, a pesar del amplio consenso de que la mayoría de las redes empíricas son, de hecho, escasas. Sin embargo, sí existe un concepto formal de escasez en el caso de modelos de redes infinitas, determinado por el comportamiento del número de aristas (L) y/o el grado promedio ( ⟨k⟩ ) a medida que el número de nodos (N) tiende a infinito. ^{[ 2 ]}

Una red simple no ponderada de tamaño${\displaystyle N}$ Se denomina disperso si el número de enlaces${\displaystyle L}$en él es mucho menor que el número máximo posible de enlaces${\displaystyle L_{max}}$: ^{[ 1 ]}

${\displaystyle L\ll L_{max}={N \choose 2}}$.

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

Sin embargo, si nos ocupamos de una secuencia de grafos sintéticos${\displaystyle G_{N}}$o un modelo de red que esté bien definido para redes${\displaystyle G_{N}}$de cualquier tamaño N = 1,2,...,${\displaystyle \infty }$, entonces el${\displaystyle \ll }$adquiere su significado formal habitual:

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

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

${\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 aquellas cuyo grado promedio es constante o converge a una constante. Algunos autores llaman dispersas solo a este tipo de redes, 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 escasez de red que requieren la convergencia de la distribución de grados en${\displaystyle G_{N}}$hasta un límite bien definido en${\displaystyle N\rightarrow \infty }$. ^{[ 5 ]} Según esta definición, el gráfico de N estrellas${\displaystyle S_{N}}$, por ejemplo, no es escaso.

La distribución del grado de los nodos cambia con el aumento de la conectividad. Diferentes densidades de enlaces en las redes complejas tienen diferentes distribuciones de grado de nodos, como sugiere el análisis de redes de Flickr. ^{[ 6 ]} Las redes escasamente conectadas tienen una distribución de ley de potencias libre de escala . Con el aumento de la conectividad, las redes muestran una divergencia creciente de la ley de potencias. Uno de los principales factores que influyen 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 conectadas entre sí si comparten antecedentes sociales, intereses, gustos, creencias, etc. En el contexto de las redes biológicas, las proteínas u otras moléculas están conectadas si tienen un ajuste exacto o complementario de sus superficies complejas. ^{[ 6 ]}

Si los nodos de las redes no tienen peso, 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, se denomina matriz dispersa . Por el contrario, si la mayoría de los elementos son distintos de cero, la matriz es densa . La dispersión o densidad de la matriz se identifica por la proporción de elementos cero respecto al número total de elementos de la matriz. De forma similar, en el contexto de la teoría de grafos , si el número de enlaces se aproxima a su máximo, el grafo se conoce como grafo denso . Si el número de enlaces es inferior al máximo, este tipo de grafos se denominan grafos dispersos . ^{[ 7 ]}

Las redes dispersas se pueden encontrar en redes sociales , informáticas y biológicas , así como sus aplicaciones en redes de transporte , líneas eléctricas, citas, etc. Dado que la mayoría de las redes reales son grandes y dispersas, se han desarrollado varios modelos para comprenderlas y analizarlas. ^{[ 8 ]} Estas redes han inspirado el diseño de redes dispersas en chips en la ingeniería de computadoras embebidas multiprocesador .

Las redes dispersas también permiten cálculos más económicos al hacer que sea eficiente almacenar la red como una lista de adyacencia , en lugar de una matriz de adyacencia . Por ejemplo, al usar una lista de adyacencia, iterar sobre los vecinos de un nodo se puede lograr en O(L/N), mientras que con una matriz de adyacencia se logra en O(N). ^{[ 2 ]}