Eficiencia (ciencia de redes)

En la ciencia de redes , la eficiencia de una red es una medida de la eficiencia con la que intercambia información ^[1] y también se denomina eficiencia de comunicación . La idea subyacente (y suposición principal) es que cuanto más distantes estén dos nodos en la red, menos eficiente será su comunicación. El concepto de eficiencia se puede aplicar tanto a escala local como global en una red. A escala global, la eficiencia cuantifica el intercambio de información en toda la red donde la información se intercambia simultáneamente. La eficiencia local cuantifica la resistencia de una red a fallas a pequeña escala. Es decir, la eficiencia local de un nodo caracteriza qué tan bien se intercambia información entre sus vecinos cuando se elimina. ${\displaystyle i}$

La definición de eficiencia de la comunicación supone que la eficiencia es inversamente proporcional a la distancia, por lo que en términos matemáticos

${\displaystyle \epsilon _{ij}={\frac {1}{d_{ij}}}}$

donde es la eficiencia por pares de nodos en la red y es su distancia . ${\displaystyle \epsilon _{ij}}$${\displaystyle i,j\in V}$${\displaystyle G=(V,E)}$${\displaystyle d_{ij}}$

La eficiencia de comunicación promedio de la red se define entonces como el promedio de las eficiencias por pares: ^[1]${\displaystyle G}$

${\displaystyle E(G)={\frac {1}{N(N-1)}}\sum _{i\neq j\in V}{\frac {1}{d_{ij}}}}$

donde denota el número de nodos en la red. ${\displaystyle N=|V|}$

Las distancias se pueden medir de diferentes maneras, dependiendo del tipo de red. La distancia más natural para redes no ponderadas es la longitud de un camino más corto entre un nodo y , es decir, un camino más corto entre es un camino con un número mínimo de aristas y el número de aristas es su longitud. Observe que si entonces —y es por eso que la suma anterior es más de — mientras que si no hay un camino que conecte y , y su eficiencia por pares es cero. Al ser un recuento, para y por lo tanto está acotado entre 0 y 1, es decir, es un descriptor normalizado. ${\displaystyle i}$${\displaystyle j}$${\displaystyle i,j}$${\displaystyle i=j}$${\displaystyle d_{ij}=0}$${\displaystyle i\neq j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle d_{ij}=\infty }$${\displaystyle d_{ij}}$${\displaystyle i\neq j}$ ${\displaystyle d_{ij}\geq 1}$${\displaystyle E(G)}$

La distancia de ruta más corta también se puede generalizar a redes ponderadas, véase la distancia de ruta más corta ponderada , pero en este caso la eficiencia de comunicación promedio debe normalizarse adecuadamente para que sea comparable entre diferentes redes. ^{[2] [3]}${\displaystyle d_{ij}^{W}\in [0,+\infty ]}$

En ^{[1] [2]} los autores propusieron normalizar dividiéndolo por la eficiencia de una versión idealizada de la red : ${\displaystyle E(G)}$${\displaystyle G}$

${\displaystyle E_{\text{glob}}(G)={\frac {E(G)}{E(G^{\text{ideal}})}}.}$

${\displaystyle G^{\text{ideal}}}$es el grafo "ideal" en nodos donde están presentes todos los bordes posibles. En el caso no ponderado, cada borde tiene un peso unitario, es una camarilla , una red completa y . Cuando los bordes están ponderados, una condición suficiente (para tener una normalización adecuada, es decir ) en las distancias en la red ideal, llamada esta vez , es ^{[1] [2]}${\displaystyle N}$${\displaystyle G^{\text{ideal}}}$${\displaystyle E(G^{\text{ideal}})=1}$${\displaystyle E_{\text{glob}}(G)\in [0,1]}$${\displaystyle l_{ij}}$

${\displaystyle l_{ij}\leq d_{ij}}$

para . debe ser conocido (y diferente de cero) para todos los pares de nodos. Una elección común es tomarlos como las distancias geográficas o físicas en redes espaciales ^[2] o como el costo máximo sobre todos los enlaces, p. ej. donde indica la fuerza máxima de interacción en la red. ^[4] Sin embargo, en ^[3] los autores resaltan los problemas de estas elecciones cuando se trata con redes del mundo real, que se caracterizan por una estructura y flujos heterogéneos. Por ejemplo, la elección hace que la medida global sea muy sensible a los valores atípicos en la distribución de pesos y tiende a subestimar la eficiencia real de una red. Los autores también proponen un procedimiento de normalización, es decir, una forma de construir utilizando toda y solo la información contenida en los pesos de los bordes (y ningún otro metadato como las distancias geográficas), que es estadísticamente robusto y está físicamente fundamentado. ${\displaystyle i,j=1,...,N}$${\displaystyle l_{ij}}$${\displaystyle l_{ij}={\frac {1}{w_{\max }}}}$${\displaystyle w_{\max }}$${\displaystyle l_{ij}={\frac {1}{w_{\max }}}}$${\displaystyle G^{\text{ideal}}}$

La eficiencia global de una red es una medida comparable a , en lugar de simplemente la longitud de ruta promedio en sí. La distinción clave es que, mientras que mide la eficiencia en un sistema donde solo se mueve un paquete de información a través de la red, mide la eficiencia de la comunicación paralela, es decir, cuando todos los nodos intercambian paquetes de información entre sí simultáneamente. ${\displaystyle 1/L}$ ${\displaystyle L}$${\displaystyle 1/L}$${\displaystyle E_{\text{glob}}(G)}$

Se puede utilizar un promedio local de eficiencias de comunicación por pares como alternativa al coeficiente de agrupamiento de una red. La eficiencia local de una red se define como: ${\displaystyle G}$

${\displaystyle E_{loc}(G,i)={\frac {1}{N}}\sum _{i\in G}E(G_{i})}$

donde es el subgráfico local que consiste únicamente en los vecinos inmediatos de un nodo, pero no en el nodo en sí. ${\displaystyle G_{i}}$${\displaystyle i}$${\displaystyle i}$

En términos generales, la eficiencia de una red se puede utilizar para cuantificar el comportamiento de mundo pequeño en redes. La eficiencia también se puede utilizar para determinar estructuras rentables en redes ponderadas y no ponderadas. ^[2] Comparando las dos medidas de eficiencia en una red con una red aleatoria del mismo tamaño para ver cuán económica es la construcción de una red. Además, la eficiencia global es más fácil de usar numéricamente que su contraparte, la longitud del camino. ^[5]

Por estas razones, el concepto de eficiencia se ha utilizado en las diversas aplicaciones de la ciencia de redes. ^{[2] [6]} La eficiencia es útil en el análisis de redes artificiales, como redes de transporte y redes de comunicaciones. Se utiliza para ayudar a determinar qué tan rentable es una construcción de red particular, así como qué tan tolerante a fallas es. Los estudios de dichas redes revelan que tienden a tener una alta eficiencia global, lo que implica un buen uso de los recursos, pero una baja eficiencia local. Esto se debe, por ejemplo, a que una red de metro no está cerrada y los pasajeros pueden ser desviados, por ejemplo en autobuses, incluso si una línea particular en la red está fuera de servicio. ^[1]

Más allá de las redes construidas por los humanos, la eficiencia es una métrica útil cuando se habla de redes biológicas físicas. En cualquier faceta de la biología, la escasez de recursos juega un papel clave, y las redes biológicas no son una excepción. La eficiencia se utiliza en neurociencia para analizar la transferencia de información a través de redes neuronales , donde el espacio físico y las limitaciones de recursos son un factor importante. ^[5] La eficiencia también se ha utilizado en el estudio de los sistemas de túneles de colonias de hormigas , que suelen estar compuestos por grandes habitaciones y muchos túneles extensos. ^[7] Esta aplicación a las colonias de hormigas no es demasiado sorprendente porque la gran estructura de una colonia debe servir como red de transporte para diversos recursos, principalmente los alimentos. ^[6]