La longitud de ruta promedio es un concepto en topología de red que se define como el número promedio de pasos a lo largo de las rutas más cortas para todos los pares posibles de nodos de red . Es una medida de la eficiencia de la información o el transporte masivo en una red.
Concepto
La longitud de ruta promedio es una de las tres medidas más sólidas de topología de red, junto con su coeficiente de agrupamiento y su distribución de grados . Algunos ejemplos son: la cantidad promedio de clics que lo llevarán de un sitio web a otro, o la cantidad de personas con las que tendrá que comunicarse, en promedio, para contactar a un completo extraño. No debe confundirse con el diámetro de la red, que se define como la geodésica más larga , es decir, la ruta más larga y corta entre dos nodos cualesquiera de la red (consulte Distancia (teoría de grafos) ).
La longitud de camino promedio distingue una red fácilmente negociable de otra, que es complicada e ineficiente, siendo más deseable una longitud de camino promedio más corta. Sin embargo, la longitud de la ruta promedio es simplemente la longitud de la ruta más probable. La red en sí puede tener algunos nodos conectados de forma muy remota y muchos nodos, que son vecinos entre sí.
Definición
Considere un gráfico dirigido no ponderado con el conjunto de vértices . Dejar, dónde denotar la distancia más corta entre y . Asumir que Si no se puede llegar desde . Entonces, la longitud promedio del camino es:
dónde es el número de vértices en .
Aplicaciones
En una red real como Internet , una longitud de ruta media corta facilita la transferencia rápida de información y reduce los costes. La eficiencia de la transferencia de masa en una red metabólica se puede juzgar mediante el estudio de su longitud de trayectoria promedio. Una red de red eléctrica tendrá menos pérdidas si se minimiza su longitud de ruta promedio.
La mayoría de las redes reales tienen una longitud de camino promedio muy corta que conduce al concepto de un mundo pequeño donde todos están conectados con todos los demás a través de un camino muy corto.
Como resultado, la mayoría de los modelos de redes reales se crean teniendo en cuenta esta condición. Uno de los primeros modelos que intentó explicar las redes reales fue el modelo de red aleatoria . Más tarde fue seguido por el modelo Watts y Strogatz , e incluso más tarde aparecieron las redes sin escala que comenzaron con el modelo BA . Todos estos modelos tenían una cosa en común: todos predijeron una longitud de trayectoria promedio muy corta. Las longitudes de ruta promedio de algunas redes se enumeran en la Tabla. [1]. [1]
La longitud media de la ruta depende del tamaño del sistema, pero no cambia drásticamente con él. La teoría de la red del mundo pequeño predice que la longitud de la ruta promedio cambia proporcionalmente a log n, donde n es el número de nodos en la red.
Referencias
- ^ Barabási, A.-L. y R. Albert, 2002, Rev. Mod. Phys. 74, 47.