Разработка программного обеспечения для анализа и моделирования взвешенных сетей
Введение
Активно развивающаяся в последнее время теория
сложных сетей позволяет понять и количественно характеризовать многие свойства
окружающего нас мира. К сложным сетям относятся сети социальных и экономических
связей, сети трафика транспорта, энергии, информации и многое другое. Основная
цель изучения сетей - разработка алгоритмов для управления, оптимизации и
предсказания процессов в сетях.
Однако, как давно было признано, многие сети являются
существенно взвешенными, их ребра имеют различную силу. В социальных сетях
между людьми могут быть более сильные или более слабые социальные связи. В сети
метаболизма может быть больший или меньший поток вдоль частных путей реакции. В
пищевых сетях может быть больший или меньший энергетический или углеродный поток
между парами жертва-хищника. Весам ребер в сетях уделяется в физической
литературе относительно небольшое внимание по той исключительной причине, что в
любой области рекомендуется рассмотреть сначала простые случаи (невзвешенные
сети) и только потом перейти к более сложным (взвешенные сети). С другой
стороны, есть много случаев, когда веса ребер сети известны, и игнорировать их
- значит отбросить много данных, которые, по меньшей мере теоретически, могли
бы помочь нам лучше понять эти системы.
Данная работа посвящена разработке программного
обеспечения для анализа и моделирования взвешенных сетей.
1. Теоретико-аналитическая часть
Взвешенная сеть представляет собой сеть, где связи между
узлами имеют веса, привязанные к ним. Сеть представляет собой систему, элементы
которой так или иначе связаны. Элементы системы представлены в виде узлов
(вершин) и связей (ребер) между ними. Узлы могут быть нейронами, индивидами,
группами, организациями, аэропортами или даже странами, тогда как связь может
осуществляться в форме дружбы, общения, сотрудничества, союза, поток или
торговли.
В ряде реальных сетей не все связи в сети имеют одинаковую
мощность. На самом деле, связи часто ассоциируются с весами, которые отличают
их по своей силе, интенсивности или мощности. С одной стороны, сила социальных
отношений в социальных сетях - это показатель их продолжительности,
эмоциональной напряженности, интимности и обмена услугами. С другой стороны,
для несоциальных сетей, вес часто ссылается на функцию, выполняемую связью, например,
поток углерода между видами в пищевых цепях, количество синапсов в нейронных
сетях или объем трафика, проходящего по связям в транспортных сетях.
1.1
Основные характеристики
Степень узла. В современной теории сетей число связей узла
называется степенью (degree). Как видно из рисунка 1, узел A имеет степень пять,
остальные узлы - степень три. Понятие степень является локальной
характеристикой графа [1].
Рис. 1. Невзвешенный граф
Матрица смежности. Сетевые структуры можно
описывать в матричной форме. Сеть из N узлов описывается квадратной матрицей
смежности a
размерности , в которой ненулевые элементы матрицы обозначают
наличие связей между соответствующими узлами. Для неориентированных сетей
недиагональный элемент матрицы смежности равен числу связей между
узлами i и j, и, следовательно, матрица для такой сети симметрична.
Предполагается, что петли единичной длины и кратные связи запрещены, следовательно,
значения диагональных элементов равны нулю [1].
На рисунке 2 показан пример матрицы
смежности для соответствующей сети.
Рис. 2. Матрица смежности
Распределение степеней. Функция
распределения степеней узлов P(k) - вероятность того, что узел i имеет степень ki = k [2].
. (1)
Кластеризация. Кластеризация - это локальная характеристика
сети. Она характеризует степень взаимодействия между собой ближайших соседей
данного узла. В большинстве сетей, если узел А соединен с узлом В, а узел В-с
узлом С, то существует большая вероятность, что узел А соединен с узлом С
(друзья наших друзей обычно также являются и нашими друзьями).
Коэффициент кластеризации данного узла есть вероятность того,
что два ближайших соседа этого узла сами есть ближайшие соседи. Другими
словами, если узел j имеет ближайших соседей с числом связей между ними, то
локальный коэффициент кластеризации равен:
. (2)
Число есть суммарное число треугольников - циклов
длины 3 - прикрепленных к узлу j, а - максимально возможное
число треугольников. Если все ближайшие соседи узла j взаимосвязаны, то .
Когда между ними нет связей (как у деревьев), то .
Кластеризация всей сети определяется как:
, (3)
где - число треугольников в сети, а - число связанных триад,
где «связанная триада» означает узел и два его ближайших соседа [1].
Рис. 3. Кластеризация
На рисунке 3 показан пример кластеризации. Данная сеть
состоит из одного треугольника и восьми «вилок», (под «вилкой» понимают вершину
с двумя ребрами), поэтому коэффициент кластеризации для заданной сети будет
равен:
. (4)
Вес ребра. Это значение, поставленное в
соответствие данному ребру взвешенной сети. Сумма весов всех связей узла i называется силой этого
узла.
Матрица весов. Вариант матрицы смежности
для взвешенной сети, представляет собой квадратную матрицу a размерности (N - число вершин), элемент которой равен
весу ребра , если таковое имеется в сети; в противном случае
элемент полагается
равным нулю или бесконечности в зависимости от решаемой задачи. На рисунке 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 показан пример работы модели.
Рис. 8. Иллюстрация модели WGP
2.
Проектирование и реализация
Сложные сети реального мира содержат множество узлов и ребер.
Для их моделирования и анализа необходимо специальное программное обеспечение.
Для пользователя важно, чтобы приложение обладало определенным набором функций.
Таким образом, можно выделить основные требования к системе.
2.1
Общие требования к интерфейсу
Пользовательский интерфейс представляет собой совокупность
методов и средств, при помощи которых пользователь взаимодействует с множеством
элементов системы. Требования к пользовательскому интерфейсу можно разбить на
две группы:
1. Требования к внешнему виду и формам взаимодействия с
пользователем;
2. Требования по доступу к внутренней функциональности
системы при помощи пользовательского интерфейса.
К системе должно прилагаться руководство пользования -
документ, предоставляющий помощь в использовании системы.
Пользовательский интерфейс должен быть интуитивно понятным.
Под этим подразумевается, что пользователь обращается к руководству не чаще,
чем раз в десять минуть на этапе обучения и что доступ к любой функции системы
осуществляется не более чем за пять щелчков мыши.
2.2
Функциональные требования
Приложение должно иметь возможности:
. генерировать сети;
. вычислять основные характеристики:
.1. распределение степеней;
.2. коэффициент кластеризации;
.3. распределение сил узлов;
. строить графики зависимостей основных характеристик;
. сохранять и загружать смоделированные сети;
. сохранять результаты анализа сетей.
2.3
Выбор среды разработки
Для разработки был выбран объектно-ориентированный язык C#. Используемый в нем
механизм наследования позволяет описывать классы на основе уже существующего
(родительского), при этом свойства и функциональность родительского класса
заимствуются новым классом. Это позволяет структурировать объекты системы, тем
самым облегчая доступ к полям и функциям наследуемых объектов.
Выбранная среда разработки накладывает следующие требования к
ЭВМ:
1. Операционная система Windows XP или более поздняя
версия;
2. Для работы приложения необходима установленная
программная платформа.NET Framework версии 3.5 или выше.
Структура
приложения
Рис. 9. Контекстная диаграмма
Разрабатываемое приложение позволяет моделировать взвешенные
и невзвешенные сети, а также дает возможность проводить их анализ. Для этого
пользователю нужно ввести необходимые параметры, которые зависят от выбранной
модели. Моделирование проводится по 4 алгоритмам:
1. алгоритм модели Эрдеша-Реньи:
1) в начальный момент времени в сети изолированных вершин;
) с некоторой вероятностью вершины сети связываются
между собой.
2. алгоритм модели
Альберта-Барабаси:
1) в начальный момент времени в сети изолированных вершин, ;
) на каждом шаге добавляется новый узел t с m ребрами, ;
) новая вершина связывается с уже существующими с
вероятностью, пропорциональной числу связей узлов в сети:
(7)
матрица смежность программный веспиньяни
Алгоритм модели BBV
(Баррат-Бартелэмью-Веспиньяни)
В начальный момент времени в сети связанных вершин, каждая
связь имеет начальный вес ;
На каждом шаге добавляется новый узел t с m ребрами, который
присоединяется к существующей вершине i, согласно механизму группового предпочтения:
(8)
где - сила узла;
1) появление нового ребра вносит изменения в веса всей
сети. Перераспределение весов между узлами совершается по определенному
правилу,
(9)
где и [4].
Алгоритм модели взвешенного предпочтительного
присоединения:
1) в начальный момент времени в сети связанных вершин, каждая
связь имеет начальный вес ;
) на каждом шаге добавляется новый узел t с m ребрами, который
присоединяется к существующим m вершинам, согласно распределению вероятности:
(10)
где - сила узла;
3) появление нового ребра вносит изменения в веса всей
сети. Перераспределение весов между узлами совершается по определенному
правилу,
(11)
где и [4].
Смоделированную сеть можно сохранить в текстовый файл в виде
списка вершин и их соседей. В дальнейшем, сохраненные сети можно загрузить в
приложение для анализа.
Анализируются основные характеристики: распределение
степеней, распределение весов, кластеризация. Полученные данные также можно
сохранить в виде списка и визуализировать. Для распределений степеней и весов
графики строятся по логарифмической шкале.
Особенностью приложения является его открытость. Это
означает, что оно имеет возможность добавления новых моделей, характеристик для
расчета и модулей.
На рисунке 10 показана детализация работы приложения.
Рис. 10. Детализация работы системы
Главное окно программы содержит строку меню, прижатую к
верхней части окна, и рабочую область (см. рис. 11). В рабочей области
представлены выбор моделей, поля для ввода параметров, а также кнопки для
визуализации интересующих величин.
Строка меню содержит 3 пункта: «Файл», «Модули» и «Справка».
Пункт «Файл» дает доступ к функциям сохранения и загрузки (см. рис. 12).
Рис. 11. Главное окно приложения
Рис. 12. Пункт меню «Файл»
Через пункт «Модули» можно перейти к исследованию
эпидемиологических процессов или к определению структуры сообществ (см. рис.
13).
Рис. 13. Пункт меню «Модули»
Пункт меню «Справка» содержит помощь по работе и информацию о
программе (см. рис. 14).
Рис. 14. Пункт меню «Справка»
Используя созданное приложение, проведем сравнительный анализ
модели взвешенного предпочтительного присоединения и группового
предпочтительного присоединения.
Были смоделированы сети с параметрами: , где - начальное количество
узлов, - количество новых
вершин, - количество новых
ребер. На рисунках 15,16 показаны результаты для распределения степеней в
моделях BBV и WGP соответственно.
Рис. 15. Распределение степеней для модели BBV
Рис. 16. Распределение степеней для модели WGP
На рисунках 17, 18 показаны распределения весов для моделей BBV и WGP соответственно.
Рис. 17. Распределение весов для модели BBV
Рис. 18. Распределение весов для модели WGP
Заключение
В данной работе были изучены подходы к моделированию и
анализу сложных сетей и их основные характеристики. Были определены необходимые
требования к функционалу и пользовательскому интерфейсу программного обеспечения
для моделирования сетей и расчета основных характеристик.
Результатом работы является приложение для моделирования и
анализа взвешенных и невзвешенных сетей. Приложение удовлетворяет всем
предъявленным требованиям и протестировано путем моделирования сетей по
нескольким моделям. Для них были рассчитаны основные характеристики:
распределение степеней, распределение весов, кластеризация и корреляция.
Дальнейшее развитие приложения предполагает добавление новых
характеристик, а также дополнительных модулей для анализа взвешенных сетей.
Список литературы
1. И.А.
Евин. Введение в теорию сложных сетей.
2. Dorogovtesev S.N., Mendes J.F.F. Evolution of networks.
Oxford University Press, Oxford.
3. Alain Barrat, Marc
Barthe´lemy and Alessandro Vespignani. Weighted Evolving Networks:
Coupling Topology and Weight Dynamics.
. Jinying Tonga, Zhenzhong Zhanga, Rongrong Dai. Weighted
scale-free networks induced by group preferential mechanism.