Eficiencia (ciencia de redes)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En ciencia de redes, la eficiencia de una red es una medida de cuán eficientemente intercambia información y también se denomina eficiencia de comunicación. La idea subyacente (y la 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 al fallo a pequeña escala. Esa es la eficiencia local de un nodo $i$ que caracteriza qué tan bien intercambian información sus vecinos cuando se elimina.

Definición

La definición de eficiencia de comunicación asume 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 $epsilon _{{ij}}$ es la eficiencia por pares de los nodos ${ estilo de visualización i, j en V}$ en la red $G=(V,E)$ y $d_{ij}$ es su distancia.

La eficiencia de comunicación promedio de la red $GRAMO$ se define entonces como el promedio de las eficiencias por pares: ${ estilo de visualización E (G) = { fracción {1} {N (N-1)}} suma_ {i neq j en V} { fracción {1} {d_ {ij}}}}$

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

Las distancias se pueden medir de diferentes maneras, dependiendo del tipo de redes. La distancia más natural para las redes no ponderadas es la longitud de la ruta más corta entre nodos $i$ y $j$ , es decir, la ruta más corta entre $yo, j$ es una ruta con un número mínimo de aristas y la cantidad de aristas es su longitud. Observe que si ${ estilo de visualización i = j}$ entonces ${displaystyle d_{ij}=0}$ —y es por eso que la suma anterior es superior— $yoneq j$ mientras que si no hay un camino que conecte $i$ y $j$ , ${displaystyle d_{ij}=infty}$ y su eficiencia por pares es cero. Al ser $d_{ij}$ un conteo, for y so está acotado entre 0 y 1, es decir, es un descriptor normalizado. $yoneq j$ ${displaystyle d_{ij}geq 1}$ $P.EJ)$

Redes ponderadas

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

En los autores propusieron normalizar $P.EJ)$ dividiéndolo por la eficiencia de una versión idealizada de la red $GRAMO$ : ${displaystyle E_{text{glob}}(G)={frac {E(G)}{E(G^{text{ideal}})}}.}$

${displaystyle G^{text{ideal}}}$ es el gráfico "ideal" en los $norte$ nodos en los que están presentes todos los bordes posibles. En el caso no ponderado, cada borde tiene un peso unitario, ${displaystyle G^{text{ideal}}}$ es una camarilla, una red completa y ${displaystyle E(G^{text{ideal}})=1}$ . Cuando se ponderan los bordes, una condición suficiente (para tener una normalización adecuada, es decir, ${displaystyle E_{text{globo}}(G)en [0,1]}$ ) sobre las distancias en la red ideal, llamada este tiempo $l_{ij}$ , es ${displaystyle l_{ij}leq d_{ij}}$

para ${ estilo de visualización i, j = 1,..., N}$ _ $l_{ij}$ debe ser conocido (y diferente de cero) para todos los pares de nodos. Una opción común es tomarlos como las distancias geográficas o físicas en las redes espaciales o como el costo máximo de todos los enlaces, por ejemplo, ${displaystyle l_{ij}={frac{1}{w_{max }}}}$ donde ${ estilo de visualización w_ { máximo}}$ indica la máxima fuerza de interacción en la red. Sin embargo, los autores destacan los problemas de estas elecciones cuando se trata de redes del mundo real, que se caracterizan por estructuras y flujos heterogéneos. Por ejemplo, elegir ${displaystyle l_{ij}={frac{1}{w_{max }}}}$ 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 ${displaystyle G^{text{ideal}}}$ usando toda y solo la información contenida en los pesos de borde (y ningún otro metadato como distancias geográficas), que es estadísticamente sólido y físicamente fundamentado.

Eficiencia y comportamiento de mundo pequeño

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

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 $GRAMO$ se define como: ${displaystyle E_{loc}(G,i)={frac {1}{N}}sum_{iin G}E(G_{i})}$

donde $Soldado americano$ está el subgrafo local que consta solo de $i$ los vecinos inmediatos de un nodo, pero no del nodo $i$ en sí.

Aplicaciones

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

Por estas razones, el concepto de eficiencia se ha utilizado en las diversas aplicaciones de la ciencia de redes. La eficiencia es útil en el análisis de redes hechas por el hombre, como redes de transporte y redes de comunicaciones. Se utiliza para ayudar a determinar qué tan rentable es la construcción de una red en particular, así como qué tan tolerante a fallas es. Los estudios de tales 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 a que, por ejemplo, una red de metro no está cerrada y los pasajeros pueden ser desviados, por ejemplo, en autobuses, incluso si una línea en particular de la red no funciona.

Más allá de las redes construidas por 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 discutir 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. La eficiencia también se ha utilizado en el estudio de los sistemas de túneles de colonias de hormigas, que generalmente se componen de grandes salas y muchos túneles en expansión. Esta aplicación a las colonias de hormigas no es demasiado sorprendente porque la gran estructura de una colonia debe servir como una red de transporte para varios recursos, la mayoría de ellos alimentos.

Contenido relacionado

Más resultados...