Разработка программного обеспечения для анализа и моделирования взвешенных сетей
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?ти от решаемой задачи. На рисунке 4 показан пример матрицы весов для соответствующей сети.
Рис. 4. Матрица весов
1.2 Основные модели, описывающие поведение сетей
Модель случайных графов Эрдеша - Реньи. В 1959 г. Эрдеш и Реньи предложили математическую теорию случайных графов. Процесс построения сети Эрдеша и Реньи можно описать в терминах орел и решка: имеется конечное число узлов, выбирается два узла, если выпадает орел, узлы связываются между собой; в случае решки эти два узла не соединяются; далее случайно выбирается другая пара вершин, и процесс повторяется (или в более общем случае случайно выбранная пара вершин сети с вероятностью соединяется, а вероятностью не соединяется, где ). Авторы рассматривали сети с достаточно большим числом вершин и показали, что топология сети описывается биномиальным распределением.
До работ Эрдеша и Реньи теория графов концентрировалась исключительно на малых и регулярных графах, которые не содержали неопределенностей в структуре. Но при исследованиях таких сложных систем, как Интернет или клетка, регулярные графы становятся скорее исключением, чем нормой. Эрдеш и Реньи впервые показали, что большие случайные графы очень усложнены и в принципе могут быть описаны с помощью теории вероятностей.
В 1982 г. один из учеников Эрдеша - Б. Боллобас, профессор математики в Университете Мемфиса в США и в Колледже Троицы в Великобритании, рассматривал случайные сети с бесконечным числом вершин и описал форму распределения степеней (вероятность того, что случайным образом выбранная вершина имеет k ребер). Он показал, что распределение степеней для такой сети описывается распределением Пуассона. Распределение Пуассона имеет характерный максимум, указывающий на то, что узлы сети в среднем имеют примерно одинаковое число связей. По обе стороны пика распределение быстро спадает, отклоняясь достаточно мало от среднего значения.
Модель сети с предпочтительным присоединением. В 1999 г. Барабаси и Альберт предложили модель растущей сети, основанную на двух принципах:
) рост: начинаем с небольшого числа () вершин, на каждом временном шаге к сети добавляется новая вершина, которая связывается ( ) ребрами с уже существующими в системе вершинами;
Рис. 5. Распределение степеней для случайных графов. N = 1000, p = 0.5
2) предпочтительное присоединение: вероятность того, что новая вершина окажется связанной ребром с вершиной пропорциональна ее степени:
(5)
С помощью этой модели, объединяющей рост и предпочтительное присоединение, удалось генерировать сеть с масштабно-инвариантным распределением степеней. Но, к сожалению, масштабно-инвариантная модель не могла в полной мере воспроизвести реальные сети. Хотя она порождала сеть со степенным распределением степеней , значение показателя степени в ней оказывалось фиксированным - , в то время как для сетей реального мира значение находится в интервале от 2 до 3. Многие эффекты, а именно: появление новых случайных связей, исчезновение узлов и связей и пересвязывание, в этой модели были для простоты проигнорированы. Тем не менее, масштабно-инвариантная модель вызвала огромный интерес и в дальнейшем были предложены различные ее модификации.
Рис. 6. Модель предпочтительного присоединения
Модель взвешенного предпочтительного присоединения. Модель роста взвешенных сетей, которая объединяет добавление новых ребер и вершин и динамическое изменение весов. Модель основана на простой динамике весов и создает сеть, представляющую статистические свойства, которые наблюдаются в нескольких реальных системах. В частности, модель дает нетривиальную эволюцию во времени свойств вершин и масштабно-инвариантное поведение распределений весов, сил и степеней [3]. Модель была предложена А. Барратом, М. Бартелэмью и А. Веспиньяни (BBV).
Присоединение новых вершин совершается согласно распределению вероятностей:
(6)
где - сила узла. Добавление новых узлов приводит к перераспределению весов в сети по определенному правилу. На рисунке 7 показано это правило.
Рис. 7. Перераспределение весов
Взвешенное присоединение - подходящий механизм для многих технологических сетей. В Интернете, новые маршрутизаторы подключаются к лучшим маршрутизаторам с точки зрения пропускной способности и возможности обработки передачи данных, а в сетях аэропортов новые соединения, как правило, устанавливаются с аэропортами с большими пассажирскими потоками [3].
Модель взвешенного группового предпочтительного присоединения. Баррат и соавторы реализовали модель, которая учитывает сочетание изменение во времени топологии и весов, и которая, возможно, самая простая в классе взвешенных растущих сетей. Новизна в модели - динамическое изменение весов, возникающей при добавлении в сеть новых вершин и ребер. Этот простой механизм создает широкий спектр сложного и масштабно-инвариантного поведения [4].
На основе модели BBV предлагается модель взвешенного группового предпочтительного присоединения (WGP).
В этой модели развитие динамики весов, возникающей при добавлении в сеть новых ребер и вершин и, особенно, выбор нового узла для присоединения происходит согласно механизму группового предпочтения, а именно: для каждого нового узла, выбор целевых узлов происходит в соответствии с их общим весом, а не каждого узла отдельно [4]. На рисунке 8 показан пример работы модели.
&nbs