Меню Главная Случайная статья Настройки Средняя длина пути Материал из https://ru.wikipedia.org Средняя длина пути, или средняя длина кратчайшего пути — это концепция в сетевой топологии которая определяется как среднее число шагов вдоль кратчайших путей для всех возможных пар узлов сети. Это показатель эффективности переноса информации или массы в сети. Содержание 1 Концепция 2 Определение 3 Приложения 4 Примечания Концепция Средняя длина пути является одной из трёх наиболее надёжных характеристик топологии сети, наряду с коэффициентом кластеризации и распределением степеней вершин. Примерами могут служить: среднее число кликов которые ведут с одного веб-сайта на другой, или среднее количество людей, через которых придётся пройти, чтобы связаться с совершенно незнакомым человеком. Не следует путать показатель с диаметром сети, который определяется как самая длинная геодезическая, то есть самый длинный кратчайший путь между любыми двумя узлами сети (см. Метрика кратчайшего пути). Средняя длина пути позволяет отличить легко проходимую сеть от сложной и неэффективной при предпочтении меньшей средней длины пути. Однако, средняя длина пути — это просто просто наиболее вероятная длина пути. Сама сеть может иметь очень удалённые друг от друга узлы, так и множество узлов, являющихся соседями друг другу. Определение Рассмотрим невзвешенный ориентированный граф ${\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}={\tfrac {1}{n(n-1)}}\sum _{i\neq j}d(v_{i},v_{j}),}$ где ${\displaystyle n}$ равно числу вершин в ${\displaystyle G}$. Приложения В реальной сети, такой как интернет, короткая средняя длина пути способствует быстрой передаче информации и снижает затраты. Эффективность переноса массы в метаболической сети[англ.] можно оценить, изучив её среднюю длину пути. Электрическая сеть будет иметь меньшие потери, если её средняя длина пути будет минимизирована. Большинство реальных сетей имеют очень короткую среднюю длину пути, что приводит к концепции «Мир тесен»[англ.], где каждый связан с остальными очень короткими путями. В результате, большинство моделей реальных сетей создаются с учётом этого условия. Одной из первых моделей, которая попыталась объяснить реальные сети, была была модель случайной сети. Позже появилась модель Уоттса и Строгаца[англ.], а ещё позже модель безмасштабных сетей, начиная с модели Барабаши — Альберта. Все эти модели имели одну общую черту — все они предсказывали очень короткую среднюю длину пути[1]. Средняя длина пути зависит от размера системы, но не меняется радикально с его изменением. Теория «Мир тесен» предсказывает, что средняя длина пути изменяется пропорционально log n, где n — число узлов сети. Примечания Barabsi, A.-L., and R. Albert, 2002, Rev. Mod. Phys. 74, 47.