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

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

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

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

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

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

где — количество вершин в .${\displaystyle n}$${\displaystyle G}$

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

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

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

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