Разработка программного обеспечения для анализа и моделирования взвешенных сетей
Содержание
Введение
Теоретико-аналитическая часть
Основные характеристики
Основные модели, описывающие
поведение сетей
Проектирование и реализация
Общие требования к интерфейсу
Функциональные требования
Выбор среды разработки
Структура приложения
Реализация
Анализ результатов
Заключение
Список литературы
Введение
Активно развивающаяся в последнее время теория сложных сетей
позволяет понять и количественно характеризовать многие свойства окружающего
нас мира. К сложным сетям относятся сети социальных и экономических связей,
сети трафика транспорта, энергии, информации и многое другое. Основная цель
изучения сетей - разработка алгоритмов для управления, оптимизации и
предсказания процессов в сетях.
Однако, как давно было признано, многие сети являются существенно
взвешенными, их ребра имеют различную силу. В социальных сетях между людьми
могут быть более сильные или более слабые социальные связи. В сети метаболизма
может быть больший или меньший поток вдоль частных путей реакции. В пищевых
сетях может быть больший или меньший энергетический или углеродный поток между
парами жертва-хищника. Весам ребер в сетях уделяется в физической литературе
относительно небольшое внимание по той исключительной причине, что в любой
области рекомендуется рассмотреть сначала простые случаи (невзвешенные сети) и
только потом перейти к более сложным (взвешенные сети). С другой стороны, есть
много случаев, когда веса ребер сети известны, и игнорировать их - значит
отбросить много данных, которые, по меньшей мере теоретически, могли бы помочь
нам лучше понять эти системы.
Данная работа посвящена разработке программного обеспечения
для анализа и моделирования
взвешенных сетей.
Теоретико-аналитическая
часть
Взвешенная сеть представляет собой сеть, где связи между узлами имеют
веса, привязанные к ним. Сеть представляет собой систему, элементы которой так
или иначе связаны. Элементы системы представлены в виде узлов (вершин) и связей
(ребер) между ними. Узлы могут быть нейронами, индивидами, группами,
организациями, аэропортами или даже странами, тогда как связь может
осуществляться в форме дружбы, общения, сотрудничества, союза, поток или
торговли.
В ряде реальных сетей не все связи в сети имеют одинаковую мощность. На
самом деле, связи часто ассоциируются с весами, которые отличают их по своей
силе, интенсивности или мощности. С одной стороны, сила социальных отношений в
социальных сетях - это показатель их продолжительности, эмоциональной
напряженности, интимности и обмена услугами. С другой стороны, для несоциальных
сетей, вес часто ссылается на функцию, выполняемую связью, например, поток
углерода между видами в пищевых цепях, количество синапсов в нейронных сетях
или объем трафика, проходящего по связям в транспортных сетях.
Основные характеристики
Степень узла. В современной теории сетей число связей узла называется
степенью (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. Матрица весов
Основные модели, описывающие
поведение сетей
Модель
случайных графов Эрдеша - Реньи. В
1959 г. Эрдеш и Реньи предложили математическую теорию случайных графов.
Процесс построения сети Эрдеша и Реньи можно описать в терминах «орел и решка»:
имеется конечное число узлов, выбирается два узла, если выпадает орел, узлы
связываются между собой; в случае решки эти два узла не соединяются; далее
случайно выбирается другая пара вершин, и процесс повторяется (или в более
общем случае случайно выбранная пара вершин сети с вероятностью 
соединяется, а вероятностью 
не соединяется, где 
). Авторы
рассматривали сети с достаточно большим числом вершин и показали, что топология
сети описывается биномиальным распределением.
До
работ Эрдеша и Реньи теория графов концентрировалась исключительно на малых и
регулярных графах, которые не содержали неопределенностей в структуре. Но при
исследованиях таких сложных систем, как Интернет или клетка, регулярные графы
становятся скорее исключением, чем нормой. Эрдеш и Реньи впервые показали, что
большие случайные графы очень «усложнены» и в принципе могут быть описаны с
помощью теории вероятностей.
В
1982 г. один из учеников Эрдеша - Б. Боллобас, профессор математики в
Университете Мемфиса в США и в Колледже Троицы в Великобритании, рассматривал
случайные сети с бесконечным числом вершин и описал форму распределения
степеней (вероятность того, что случайным образом выбранная вершина имеет k
ребер). Он показал, что распределение степеней для такой сети описывается
распределением Пуассона. Распределение Пуассона имеет характерный максимум,
указывающий на то, что узлы сети в среднем имеют примерно одинаковое число
связей. По обе стороны пика распределение быстро спадает, отклоняясь достаточно
мало от среднего значения (см. рис. 5).
Рис. 5.
Распределение степеней для случайных графов. N = 1000, p = 0.5
Модель сети с предпочтительным присоединением. В 1999 г. Барабаси и Альберт
предложили модель растущей сети, основанную на двух принципах:
) рост: начинаем с небольшого числа (
) вершин, на каждом временном шаге к
сети добавляется новая вершина, которая связывается 
(£ ) ребрами с уже существующими в системе вершинами;
2)
предпочтительное присоединение: вероятность того, что новая вершина окажется
связанной ребром с вершиной 
пропорциональна
ее степени:
(5)
С
помощью этой модели, объединяющей рост и предпочтительное присоединение,
удалось генерировать сеть с масштабно-инвариантным распределением степеней. Но,
к сожалению, масштабно-инвариантная модель не могла в полной мере воспроизвести
реальные сети. Хотя она порождала сеть со степенным распределением степеней 
, значение показателя степени в ней оказывалось
фиксированным - 
, в то время как для сетей реального мира значение 
находится в интервале от 2 до 3. Многие эффекты, а
именно: появление новых случайных связей, исчезновение узлов и связей и
пересвязывание, в этой модели были для простоты проигнорированы. Тем не менее,
масштабно-инвариантная модель вызвала огромный интерес и в дальнейшем были
предложены различные ее модификации (см. рис. 6).
Рис. 6.
Модель предпочтительного присоединения
Модель взвешенного предпочтительного присоединения. Модель роста взвешенных сетей,
которая объединяет добавление новых ребер и вершин и динамическое изменение
весов. Модель основана на простой динамике весов и создает сеть, представляющую
статистические свойства, которые наблюдаются в нескольких реальных системах. В
частности, модель дает нетривиальную эволюцию во времени свойств вершин и
масштабно-инвариантное поведение распределений весов, сил и степеней [3].
Модель была предложена А. Барратом, М. Бартелэмью и А. Веспиньяни (BBV).
Присоединение новых вершин совершается согласно распределению
вероятностей:
(6)
где 
- сила узла. Добавление новых узлов приводит к
перераспределению весов в сети по определенному правилу. На рисунке 7 показано это правило.
Рис. 7.
Перераспределение весов
Взвешенное присоединение - подходящий механизм для многих технологических
сетей. В Интернете, новые маршрутизаторы подключаются к лучшим маршрутизаторам
с точки зрения пропускной способности и возможности обработки передачи данных,
а в сетях аэропортов новые соединения, как правило, устанавливаются с
аэропортами с большими пассажирскими потоками [3].
Модель взвешенного группового предпочтительного присоединения. Баррат и соавторы реализовали
модель, которая учитывает сочетание изменение во времени топологии и весов, и
которая, возможно, самая простая в классе взвешенных растущих сетей. Новизна в
модели - динамическое изменение весов, возникающей при добавлении в сеть новых
вершин и ребер. Этот простой механизм создает широкий спектр сложного и
масштабно-инвариантного поведения [4].
В этой модели развитие динамики весов, возникающей при добавлении в сеть
новых ребер и вершин и, особенно, выбор нового узла для присоединения
происходит согласно механизму группового предпочтения, а именно: для каждого
нового узла, выбор целевых узлов происходит в соответствии с их общим весом, а
не каждого узла отдельно [4]. На рисунке 8 показан пример работы модели.
Рис. 8.
Иллюстрация модели WGP
Проектирование и реализация
Сложные сети реального мира содержат множество узлов и ребер. Для их
моделирования и анализа необходимо специальное программное обеспечение. Для
пользователя важно, чтобы приложение обладало определенным набором функций.
Таким образом, можно выделить основные требования к системе.
Общие требования к интерфейсу
Пользовательский интерфейс представляет собой совокупность методов и
средств, при помощи которых пользователь взаимодействует с множеством элементов
системы. Требования к пользовательскому интерфейсу можно разбить на две группы:
1. Требования к внешнему виду и формам взаимодействия с пользователем;
2. Требования по доступу к внутренней функциональности системы при
помощи пользовательского интерфейса.
К системе должно прилагаться руководство пользования - документ,
предоставляющий помощь в использовании системы.
Пользовательский интерфейс должен быть интуитивно понятным. Под этим
подразумевается, что пользователь обращается к руководству не чаще, чем раз в
десять минуть на этапе обучения и что доступ к любой функции системы
осуществляется не более чем за пять щелчков мыши.
Функциональные требования
Приложение должно иметь возможности:
. генерировать сети;
. вычислять основные характеристики:
.1. распределение степеней;
.2. коэффициент кластеризации;
.3. распределение сил узлов;
. строить графики зависимостей основных характеристик;
. сохранять и загружать смоделированные сети;
. сохранять результаты анализа сетей.
Выбор среды разработки
Для разработки был выбран объектно-ориентированный язык C#. Используемый в нем механизм наследования позволяет
описывать классы на основе уже существующего (родительского), при этом свойства
и функциональность родительского класса заимствуются новым классом. Это
позволяет структурировать объекты системы, тем самым облегчая доступ к полям и
функциям наследуемых объектов.
Язык C# содержит богатый инструментарий для
создания многофункционального пользовательского интерфейса, поэтому, в
настоящее время, широко используется в разработке оконных приложений.
Выбранная среда разработки накладывает следующие требования к ЭВМ:
1. Операционная система Windows XP или более поздняя версия;
2. Для работы приложения необходима установленная программная
платформа .NET Framework версии 3.5 или выше.
Структура приложения
Рис.9.
Контекстная диаграмма
Разрабатываемое приложение позволяет моделировать взвешенные и
невзвешенные сети, а также дает возможность проводить их анализ. Для этого
пользователю нужно ввести необходимые параметры, которые зависят от выбранной
модели. Моделирование проводится по 4 алгоритмам:
1. алгоритм модели Эрдеша-Реньи:
1) в начальный момент времени в сети 
изолированных вершин;
) с некоторой вероятностью 
вершины сети связываются между
собой.
2. алгоритм модели Альберта-Барабаси:
1) в начальный момент времени в сети изолированных вершин, 
;
) на каждом шаге добавляется новый узел t с m ребрами, 
;
) новая вершина связывается с уже существующими с вероятностью,
пропорциональной числу связей узлов в сети:
(7)
3. алгоритм модели BBV (Баррат-Бартелэмью-Веспиньяни):
1) в начальный момент времени в сети связанных вершин, каждая связь имеет
начальный вес 
;
) на каждом шаге добавляется новый узел t с m ребрами, который присоединяется к существующей
вершине i, согласно механизму группового
предпочтения:
(8)
где - сила узла;
3) появление нового ребра вносит изменения в веса всей сети.
Перераспределение весов между узлами совершается по определенному правилу,
(9)
где 
и 
[4].
4. алгоритм модели взвешенного
предпочтительного присоединения:
1) в начальный момент времени в сети связанных вершин, каждая связь имеет
начальный вес ;
) на каждом шаге добавляется новый узел t с m ребрами, который присоединяется к существующим m вершинам, согласно распределению
вероятности:
(10)
где - сила узла;
3) появление нового ребра вносит изменения в веса всей сети.
Перераспределение весов между узлами совершается по определенному правилу,
(11)
где и [4].
Смоделированную сеть можно сохранить в текстовый файл в виде списка
вершин и их соседей. В дальнейшем, сохраненные сети можно загрузить в
приложение для анализа.
Анализируются основные характеристики: распределение степеней,
распределение весов, кластеризация. Полученные данные также можно сохранить в
виде списка и визуализировать. Для распределений степеней и весов графики
строятся по логарифмической шкале.
Особенностью приложения является его открытость. Это означает, что оно
имеет возможность добавления новых моделей, характеристик для расчета и
модулей.
На рисунке 10 показана детализация работы приложения.
Рис. 10. Детализация
работы системы
Реализация
Главное окно программы содержит строку меню, прижатую к верхней части
окна, и рабочую область (см. рис. 11). В рабочей области представлены выбор
моделей, поля для ввода параметров, а также кнопки для визуализации интересующих
величин.
Рис.11.
Главное окно приложения
Строка меню содержит 3 пункта: «Файл», «Модули» и «Справка». Пункт «Файл»
дает доступ к функциям сохранения и загрузки (см. рис. 12).
Рис. 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.
4. Jinying Tonga, Zhenzhong Zhanga, Rongrong
Dai. Weighted scale-free networks induced by group preferential mechanism.