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

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

Концепция [ править ]

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

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

Определение [ править ]

Рассмотрим невзвешенный ориентированный граф с множеством вершин . Пусть , где обозначает кратчайшее расстояние между и . Предположим, что если недоступен из . Тогда средняя длина пути равна:${\ 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]. ^[1]

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

Ссылки [ править ]