Повна версія

Головна arrow Інформатика arrow Моделирование сложных сетей

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Кратчайший путь между узлами

Расстояние между узлами определяется как количество шагов, которые необходимо сделать, чтобы по существующим ребрам добраться от одного узла до другого. Естественно, узлы могут быть соединены прямо или опосредованно, через другие узлы.

Кратчайшим путем (SP, shortest path) между узлами назовем минимальное расстояние между ними. Для всей сети можно ввести понятие среднего кратчайшего пути, как среднее по всем парам узлов минимальное расстояния между ними:

где п - количество узлов, -кратчайшее расстояние между узлами

П. Эрдешем (Р. Егсіоб) и А. Реньи (А. Кепуі) было показано, что средний кратчайший путь в случайном графе растет медленно - как логарифм от числа узлов.

Пауль Эрдеш

Пауль Эрдеш (1913-1996)

Erdas, P., Renyi A. On Random Graphs. Publicationes Mathematicae, 1959. - № 6. - pp. 290297.

Erdas P., Renyi A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci.,

1960. - № 5. - pp.17-61. - 1960.

С именем П. Эрдеша связаны не только исследования сложных сетей, но и популярное число Эрдеша, которое используется как один из критериев определения уровня математиков в соответствующем социуме, базирующийся на так называемой сети соавторства. Известно, что Эрдеш написал около полутора тысяч статей, а также, что количество его соавторов превышало 500. Столь большое число соавторов и породило такое понятие, как число Эрдеша, которое определяется следующим образом: у самого Эрдеша это число равно нулю; у соавторов Эрдеша это число равно единице; соавторы людей с числом Эрдеша, равным единице, имеют число Эрдеша два; и т. д.

Таким образом, число Эрдеша это длина пути от некоторого автора до самого Эрдеша по совместным работам. Известен факт, что 90% математиков обладают числом Эрдеша не выше 8, что соответствует сетям "малых миров", речь о которых пойдет ниже.

Некоторые сети могут оказаться несвязными, т.е. найдутся узлы, расстояние между которыми окажется бесконечным. Соответственно, средний путь может оказаться также равным бесконечности. Для учета таких случаев вводится понятие среднего инверсного пути Е между узлами, рассчитываемое по формуле:

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

 
<<   ЗМІСТ   >>