Разработка программного обеспечения для анализа и моделирования взвешенных сетей

• Введение
• Теоретико-аналитическая часть
• Основные характеристики
• Основные модели, описывающие поведение сетей
• Проектирование и реализация
• Общие требования к интерфейсу
• Функциональные требования
• Выбор среды разработки
• Структура приложения
• Реализация
• Анализ результатов
• Заключение

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

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

Данная работа посвящена разработке программного обеспечения для анализа и моделирования взвешенных сетей.

Теоретико-аналитическая часть

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

В ряде реальных сетей не все связи в сети имеют одинаковую мощность. На самом деле, связи часто ассоциируются с весами, которые отличают их по своей силе, интенсивности или мощности. С одной стороны, сила социальных отношений в социальных сетях — это показатель их продолжительности, эмоциональной напряженности, интимности и обмена услугами. С другой стороны, для несоциальных сетей, вес часто ссылается на функцию, выполняемую связью, например, поток углерода между видами в пищевых цепях, количество синапсов в нейронных сетях или объем трафика, проходящего по связям в транспортных сетях.

Основные характеристики

Степень узла. В современной теории сетей число связей узла называется степенью (degree). Как видно из рисунка 1, узел A имеет степень пять, остальные узлы — степень три. Понятие степень является локальной характеристикой графа [1].

Рис. 1. Невзвешенный граф.

Матрица смежности. Сетевые структуры можно описывать в матричной форме. Сеть из N узлов описывается квадратной матрицей смежности a размерности, в которой ненулевые элементы матрицы обозначают наличие связей между соответствующими узлами. Для неориентированных сетей недиагональный элемент матрицы смежности равен числу связей между узлами i и j, и, следовательно, матрица для такой сети симметрична. Предполагается, что петли единичной длины и кратные связи запрещены, следовательно, значения диагональных элементов равны нулю [1].

На рисунке 2 показан пример матрицы смежности для соответствующей сети.

Рис. 2. Матрица смежности.

Распределение степеней. Функция распределения степеней узлов P(k) — вероятность того, что узел i имеет степень k_i = 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 г. Барабаси и Альберт предложили модель растущей сети, основанную на двух принципах:

1) рост: начинаем с небольшого числа () вершин, на каждом временном шаге к сети добавляется новая вершина, которая связывается () ребрами с уже существующими в системе вершинами;

2) предпочтительное присоединение: вероятность того, что новая вершина окажется связанной ребром с вершиной пропорциональна ее степени:

(5).

С помощью этой модели, объединяющей рост и предпочтительное присоединение, удалось генерировать сеть с масштабно-инвариантным распределением степеней. Но, к сожалению, масштабно-инвариантная модель не могла в полной мере воспроизвести реальные сети. Хотя она порождала сеть со степенным распределением степеней, значение показателя степени в ней оказывалось фиксированным —, в то время как для сетей реального мира значение находится в интервале от 2 до 3. Многие эффекты, а именно: появление новых случайных связей, исчезновение узлов и связей и пересвязывание, в этой модели были для простоты проигнорированы. Тем не менее, масштабно-инвариантная модель вызвала огромный интерес и в дальнейшем были предложены различные ее модификации (см. рис. 6).

Рис. 6. Модель предпочтительного присоединения.

Модель взвешенного предпочтительного присоединения. Модель роста взвешенных сетей, которая объединяет добавление новых ребер и вершин и динамическое изменение весов. Модель основана на простой динамике весов и создает сеть, представляющую статистические свойства, которые наблюдаются в нескольких реальных системах. В частности, модель дает нетривиальную эволюцию во времени свойств вершин и масштабно-инвариантное поведение распределений весов, сил и степеней [3]. Модель была предложена А. Барратом, М. Бартелэмью и А. Веспиньяни (BBV).

Присоединение новых вершин совершается согласно распределению вероятностей:

(6).

где — сила узла. Добавление новых узлов приводит к перераспределению весов в сети по определенному правилу. На рисунке 7 показано это правило.

Рис. 7. Перераспределение весов Взвешенное присоединение — подходящий механизм для многих технологических сетей. В Интернете, новые маршрутизаторы подключаются к лучшим маршрутизаторам с точки зрения пропускной способности и возможности обработки передачи данных, а в сетях аэропортов новые соединения, как правило, устанавливаются с аэропортами с большими пассажирскими потоками [3].

Модель взвешенного группового предпочтительного присоединения. Баррат и соавторы реализовали модель, которая учитывает сочетание изменение во времени топологии и весов, и которая, возможно, самая простая в классе взвешенных растущих сетей. Новизна в модели — динамическое изменение весов, возникающей при добавлении в сеть новых вершин и ребер. Этот простой механизм создает широкий спектр сложного и масштабно-инвариантного поведения [4].

На основе модели BBV предлагается модель взвешенного группового предпочтительного присоединения (WGP).

В этой модели развитие динамики весов, возникающей при добавлении в сеть новых ребер и вершин и, особенно, выбор нового узла для присоединения происходит согласно механизму группового предпочтения, а именно: для каждого нового узла, выбор целевых узлов происходит в соответствии с их общим весом, а не каждого узла отдельно [4]. На рисунке 8 показан пример работы модели.

Рис. 8. Иллюстрация модели WGP.

Проектирование и реализация

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

Общие требования к интерфейсу

Пользовательский интерфейс представляет собой совокупность методов и средств, при помощи которых пользователь взаимодействует с множеством элементов системы. Требования к пользовательскому интерфейсу можно разбить на две группы:

1. Требования к внешнему виду и формам взаимодействия с пользователем;

2. Требования по доступу к внутренней функциональности системы при помощи пользовательского интерфейса.

К системе должно прилагаться руководство пользования — документ, предоставляющий помощь в использовании системы.

Пользовательский интерфейс должен быть интуитивно понятным. Под этим подразумевается, что пользователь обращается к руководству не чаще, чем раз в десять минуть на этапе обучения и что доступ к любой функции системы осуществляется не более чем за пять щелчков мыши.

Функциональные требования

Приложение должно иметь возможности:

1. генерировать сети;

2. вычислять основные характеристики:

2.1. распределение степеней;

2.2. коэффициент кластеризации;

2.3. распределение сил узлов;

3. строить графики зависимостей основных характеристик;

4. сохранять и загружать смоделированные сети;

5. сохранять результаты анализа сетей.

Выбор среды разработки

Для разработки был выбран объектно-ориентированный язык C#. Используемый в нем механизм наследования позволяет описывать классы на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом. Это позволяет структурировать объекты системы, тем самым облегчая доступ к полям и функциям наследуемых объектов.

Язык C# содержит богатый инструментарий для создания многофункционального пользовательского интерфейса, поэтому, в настоящее время, широко используется в разработке оконных приложений.

Выбранная среда разработки накладывает следующие требования к ЭВМ:

1. Операционная система Windows XP или более поздняя версия;

2. Для работы приложения необходима установленная программная платформа .NET Framework версии 3.5 или выше.

Структура приложения

Рис. 9. Контекстная диаграмма Разрабатываемое приложение позволяет моделировать взвешенные и невзвешенные сети, а также дает возможность проводить их анализ. Для этого пользователю нужно ввести необходимые параметры, которые зависят от выбранной модели. Моделирование проводится по 4 алгоритмам:

1. алгоритм модели Эрдеша-Реньи:

1) в начальный момент времени в сети изолированных вершин;

2) с некоторой вероятностью вершины сети связываются между собой.

2. алгоритм модели Альберта-Барабаси:

1) в начальный момент времени в сети изолированных вершин, ;

2) на каждом шаге добавляется новый узел t с m ребрами, ;

3) новая вершина связывается с уже существующими с вероятностью, пропорциональной числу связей узлов в сети:

(7).

3. алгоритм модели BBV (Баррат-Бартелэмью-Веспиньяни):

1) в начальный момент времени в сети связанных вершин, каждая связь имеет начальный вес ;

2) на каждом шаге добавляется новый узел t с m ребрами, который присоединяется к существующей вершине i, согласно механизму группового предпочтения:

(8).

где — сила узла;

3) появление нового ребра вносит изменения в веса всей сети. Перераспределение весов между узлами совершается по определенному правилу,.

(9).

где и [4].

4. алгоритм модели взвешенного предпочтительного присоединения:

1) в начальный момент времени в сети связанных вершин, каждая связь имеет начальный вес ;

2) на каждом шаге добавляется новый узел 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.