Средняя длина пути

Средняя длина пути или средняя длина кратчайшего пути — понятие в топологии сети , которое определяется как среднее количество шагов по кратчайшим путям для всех возможных пар сетевых узлов . Это мера эффективности передачи информации или массового транспорта в сети.

Концепция

Средняя длина пути является одним из трех наиболее надежных показателей топологии сети, наряду с ее коэффициентом кластеризации и распределением степеней . Вот некоторые примеры: среднее количество кликов, которые переведут вас с одного веб-сайта на другой, или среднее количество людей, через которых вам придется общаться, чтобы связаться с совершенно незнакомым человеком. Его не следует путать с диаметром сети, который определяется как самая длинная геодезическая , т. е. самый длинный кратчайший путь между любыми двумя узлами в сети (см. Расстояние (теория графов) ).

Средняя длина пути отличает легко обсуждаемую сеть от сети, которая сложна и неэффективна, при этом более желательна более короткая средняя длина пути. Однако средняя длина пути — это просто та длина пути, которая, скорее всего, будет. Сама сеть может иметь несколько очень удаленных узлов и множество узлов, которые являются соседями друг друга.

Определение

Рассмотрим невзвешенный ориентированный граф $G$ с набором вершин $V$. Позволять $d(v_{1},v_{2})$, где $v_{1},v_{2}\in V$ обозначают кратчайшее расстояние между $v_{1}$ и $v_{2}$.Предположим, что $d(v_{1},v_{2})=0$ если $v_{2}$ невозможно добраться из $v_{1}$. Тогда средняя длина пути $l_{G}$ является:

$l_{G}={\frac {1}{n\cdot (n-1)}}\cdot \sum _{i\neq j}d(v_{i},v_{j}),$

где $n$ это количество вершин в $G$.

Приложения

В реальной сети, такой как Интернет , короткая средняя длина пути облегчает быструю передачу информации и снижает затраты. Об эффективности массопереноса в метаболической сети можно судить, изучая среднюю длину его пути. В электросетевой сети будет меньше потерь, если ее средняя длина пути будет минимизирована.

Большинство реальных сетей имеют очень короткую среднюю длину пути, что приводит к концепции маленького мира , где каждый связан со всеми остальными очень коротким путем.

В результате большинство моделей реальных сетей создаются с учетом этого условия. Одной из первых моделей, пытавшихся объяснить реальные сети, была модель случайной сети . Позже за ней последовала модель Уоттса и Строгаца , а еще позже появились безмасштабные сети, начиная с модели BA . У всех этих моделей было одно общее: все они предсказывали очень короткую среднюю длину пути.

Средняя длина пути зависит от размера системы, но существенно с ним не меняется. Теория сети маленького мира предсказывает, что средняя длина пути изменяется пропорционально log n, где n — количество узлов в сети.