Пример матрицы смежности для соответствующей сети. Функция распределения степеней узлов. Вариант матрицы смежности для взвешенной сети. Распределение степеней для случайных графов. Требования к интерфейсу. Алгоритм модели Баррат-Бартелэмью-Веспиньяни.
Аннотация к работе
К сложным сетям относятся сети социальных и экономических связей, сети трафика транспорта, энергии, информации и многое другое. Однако, как давно было признано, многие сети являются существенно взвешенными, их ребра имеют различную силу. Весам ребер в сетях уделяется в физической литературе относительно небольшое внимание по той исключительной причине, что в любой области рекомендуется рассмотреть сначала простые случаи (невзвешенные сети) и только потом перейти к более сложным (взвешенные сети). С другой стороны, есть много случаев, когда веса ребер сети известны, и игнорировать их - значит отбросить много данных, которые, по меньшей мере теоретически, могли бы помочь нам лучше понять эти системы. Взвешенная сеть представляет собой сеть, где связи между узлами имеют веса, привязанные к ним.Сеть из N узлов описывается квадратной матрицей смежности a размерности , в которой ненулевые элементы матрицы обозначают наличие связей между соответствующими узлами. В большинстве сетей, если узел А соединен с узлом В, а узел В-с узлом С, то существует большая вероятность, что узел А соединен с узлом С (друзья наших друзей обычно также являются и нашими друзьями). Кластеризация всей сети определяется как: , (3) где - число треугольников в сети, а - число связанных триад, где «связанная триада» означает узел и два его ближайших соседа [1]. Процесс построения сети Эрдеша и Реньи можно описать в терминах «орел и решка»: имеется конечное число узлов, выбирается два узла, если выпадает орел, узлы связываются между собой; в случае решки эти два узла не соединяются; далее случайно выбирается другая пара вершин, и процесс повторяется (или в более общем случае случайно выбранная пара вершин сети с вероятностью соединяется, а вероятностью не соединяется, где ). Барабаси и Альберт предложили модель растущей сети, основанную на двух принципах: 1) рост: начинаем с небольшого числа () вершин, на каждом временном шаге к сети добавляется новая вершина, которая связывается (? ) ребрами с уже существующими в системе вершинами;В данной работе были изучены подходы к моделированию и анализу сложных сетей и их основные характеристики. Были определены необходимые требования к функционалу и пользовательскому интерфейсу программного обеспечения для моделирования сетей и расчета основных характеристик.
Введение
Активно развивающаяся в последнее время теория сложных сетей позволяет понять и количественно характеризовать многие свойства окружающего нас мира. К сложным сетям относятся сети социальных и экономических связей, сети трафика транспорта, энергии, информации и многое другое. Основная цель изучения сетей - разработка алгоритмов для управления, оптимизации и предсказания процессов в сетях.
Однако, как давно было признано, многие сети являются существенно взвешенными, их ребра имеют различную силу. В социальных сетях между людьми могут быть более сильные или более слабые социальные связи. В сети метаболизма может быть больший или меньший поток вдоль частных путей реакции. В пищевых сетях может быть больший или меньший энергетический или углеродный поток между парами жертва-хищника. Весам ребер в сетях уделяется в физической литературе относительно небольшое внимание по той исключительной причине, что в любой области рекомендуется рассмотреть сначала простые случаи (невзвешенные сети) и только потом перейти к более сложным (взвешенные сети). С другой стороны, есть много случаев, когда веса ребер сети известны, и игнорировать их - значит отбросить много данных, которые, по меньшей мере теоретически, могли бы помочь нам лучше понять эти системы.
Данная работа посвящена разработке программного обеспечения для анализа и моделирования взвешенных сетей.
1. Теоретико-аналитическая часть
Взвешенная сеть представляет собой сеть, где связи между узлами имеют веса, привязанные к ним. Сеть представляет собой систему, элементы которой так или иначе связаны. Элементы системы представлены в виде узлов (вершин) и связей (ребер) между ними. Узлы могут быть нейронами, индивидами, группами, организациями, аэропортами или даже странами, тогда как связь может осуществляться в форме дружбы, общения, сотрудничества, союза, поток или торговли.
В ряде реальных сетей не все связи в сети имеют одинаковую мощность. На самом деле, связи часто ассоциируются с весами, которые отличают их по своей силе, интенсивности или мощности. С одной стороны, сила социальных отношений в социальных сетях - это показатель их продолжительности, эмоциональной напряженности, интимности и обмена услугами. С другой стороны, для несоциальных сетей, вес часто ссылается на функцию, выполняемую связью, например, поток углерода между видами в пищевых цепях, количество синапсов в нейронных сетях или объем трафика, проходящего по связям в транспортных сетях.
Вывод
В данной работе были изучены подходы к моделированию и анализу сложных сетей и их основные характеристики. Были определены необходимые требования к функционалу и пользовательскому интерфейсу программного обеспечения для моделирования сетей и расчета основных характеристик.
Результатом работы является приложение для моделирования и анализа взвешенных и невзвешенных сетей. Приложение удовлетворяет всем предъявленным требованиям и протестировано путем моделирования сетей по нескольким моделям. Для них были рассчитаны основные характеристики: распределение степеней, распределение весов, кластеризация и корреляция.
Дальнейшее развитие приложения предполагает добавление новых характеристик, а также дополнительных модулей для анализа взвешенных сетей.
Список литературы
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.