Red de gradiente

En la ciencia de redes , una red de gradiente es una subred dirigida de una red "sustrato" no dirigida donde cada nodo tiene un potencial escalar asociado y un enlace de salida que apunta al nodo con el potencial más pequeño (o más grande) en su vecindario, definido como la unión de sí mismo y sus vecinos en la red sustrato. ^{[ 2 ]}

El transporte se realiza en una red fija.${\displaystyle G=G(V,E)}$llamado grafo de sustrato. Tiene N nodos,${\displaystyle V=\{0,1,...,N-1\}}$y el conjunto de bordes${\displaystyle E=\{(i,j)|i,j\in V\}}$. Dado un nodo i , podemos definir su conjunto de vecinos en G mediante S _i ⁽¹⁾ = {j ∈ V | (i,j)∈ E}.

Consideremos también un campo escalar, h = { h ₀ , .., h _{N − 1} } definido en el conjunto de nodos V, de modo que cada nodo i tiene un valor escalar h _i asociado a él.

Gradiente ∇ h _i en una red : ∇h _i${\displaystyle =}$(i, μ(i)) es decir, la arista dirigida de i a μ(i) , donde μ ( i ) ∈ S _i ⁽¹⁾ ∪ {i}, y h _μ tiene el valor máximo en${\displaystyle {h_{j}|j\in S_{i}^{(1)}\cup {i}}}$.

Red de gradiente  : ∇${\displaystyle G=}$∇${\displaystyle G}$${\displaystyle (V,F)}$ donde F es el conjunto de aristas de gradiente en G.

En general, el campo escalar depende del tiempo, debido al flujo, las fuentes externas y los sumideros en la red. Por lo tanto, la red de gradiente ∇${\displaystyle G}$será dinámico. ^{[ 3 ]}

El concepto de red de gradiente fue introducido por primera vez por Toroczkai y Bassler (2004). ^{[ 4 ] [ 5 ]}

En general, las redes del mundo real (como los grafos de citas , Internet , las redes metabólicas celulares, la red mundial de aeropuertos), que a menudo evolucionan para transportar entidades como información, automóviles, energía, agua, fuerzas, etc., no están diseñadas globalmente; en cambio, evolucionan y crecen a través de cambios locales. Por ejemplo, si un enrutador en Internet se congestiona con frecuencia y los paquetes se pierden o se retrasan debido a ello, será reemplazado por varios enrutadores nuevos interconectados. ^{[ 1 ]}

Además, este flujo suele generarse o verse influenciado por gradientes locales de un escalar. Por ejemplo: la corriente eléctrica es impulsada por un gradiente de potencial eléctrico. En las redes de información, las propiedades de los nodos generan un sesgo en la forma en que la información se transmite de un nodo a sus vecinos. Esta idea motivó el enfoque para estudiar la eficiencia del flujo de una red mediante redes de gradiente, cuando el flujo es impulsado por gradientes de un campo escalar distribuido en la red. ^{[ 1 ] [ 3 ]}

Investigaciones recientesinvestiga la conexión entre la topología de la red y la eficiencia del flujo del transporte. ^{[ 1 ]}

En una red de gradiente, el grado de entrada de un nodo i, k _i ⁽ⁱⁿ⁾ es el número de aristas de gradiente que apuntan hacia i, y la distribución del grado de entrada es${\displaystyle R(l)=P\{k_{i}^{(in)}=l\}}$.

Cuando el sustrato G es un grafo aleatorio y cada par de nodos está conectado con probabilidad P (es decir, un grafo aleatorio de Erdős-Rényi ), los escalares h _i son iid (independientes e idénticamente distribuidos), la expresión exacta para R(l) viene dada por

${\displaystyle R(l)={\frac {1}{N}}\sum _{n=0}^{N-1}\mathrm {C} _{l}^{N-1-n}[1-p(1-p)]^{N-1-nl}[p(1-p)^{n}]^{l}]}$^{[ 3 ]}

En el límite${\displaystyle N\to \infty }$y${\displaystyle P\to 0}$La distribución de grados se convierte en una ley de potencias.

${\displaystyle R(l)\approx l^{-1}}$

Esto muestra que, en este límite, la red de gradiente de la red aleatoria es libre de escala. ^{[ 3 ]}

Además, si la red de sustrato G es libre de escala, como en el modelo de Barabási-Albert , entonces la red de gradiente también sigue la ley de potencias con el mismo exponente que los de G. ^{[ 1 ]}

El hecho de que la topología de la red subyacente influya en el nivel de congestión de la red se puede ilustrar con un ejemplo sencillo: si la red tiene una estructura en estrella, el flujo se congestionará en el nodo central, ya que este debe gestionar todo el flujo proveniente de los demás nodos. Sin embargo, si la red tiene una estructura en anillo, dado que cada nodo cumple la misma función, no se produce congestión del flujo.

Bajo el supuesto de que el flujo se genera por gradientes en la red, la eficiencia del flujo en las redes se puede caracterizar a través del factor de atasco (o factor de congestión), definido de la siguiente manera:

${\displaystyle J=1-\langle \langle {\frac {N_{\text{recibir}}}{N_{\text{enviar}}}}\rangle _{h}\rangle _{\text{red}}=R(0)}$

donde N _recibe es el número de nodos que reciben flujo de gradiente y N _envía es el número de nodos que envían flujo de gradiente. El valor de J está entre 0 y 1;${\displaystyle J=0}$significa que no hay congestión y${\displaystyle J=1}$corresponde a la congestión máxima. En el límite${\displaystyle N\to \infty }$, para un gráfico aleatorio Erdős-Rényi , el factor de congestión se convierte en

${\displaystyle J(N,P)=1-{\frac {\ln N}{N\ln({\frac {1}{1-P}})}}\left[1+O({\frac {1}{N}})\right]\rightarrow 1.}$

Este resultado muestra que las redes aleatorias se congestionan al máximo en ese límite. Por el contrario, para una red libre de escala , J es una constante para cualquier N , lo que significa que las redes libres de escala no son propensas a la congestión máxima. ^{[ 6 ]}

Un problema en las redes de comunicación es comprender cómo controlar la congestión y mantener una función de red normal y eficiente. ^{[ 7 ]}

Zonghua Liu et al. (2006) demostraron que la congestión es más probable que ocurra en los nodos con grados altos en las redes, y se demostró que un enfoque eficiente de mejorar selectivamente la capacidad de procesamiento de mensajes de una pequeña fracción (por ejemplo, el 3%) de los nodos funciona igual de bien que mejorar la capacidad de todos los nodos. ^{[ 7 ]}

Ana L Pastore y Piontti et al. (2008) demostraron que la dinámica de relajación puede reducir la congestión de la red. ^{[ 8 ]}

Pan et al. (2011) estudiaron las propiedades de atasco en un esquema donde a los bordes se les asignan pesos que son una potencia de la diferencia escalar entre los potenciales de los nodos. ^{[ 9 ]}

Niu y Pan (2016) demostraron que la congestión puede reducirse introduciendo una correlación entre el campo de gradiente y la topología de la red local. ^{[ 10 ]}

• dinámica de redes
• Topología de red
• Red compleja cuántica