Разработка программного обеспечения для анализа и моделирования взвешенных сетей
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Введение
Активно развивающаяся в последнее время теория сложных сетей позволяет понять и количественно характеризовать многие свойства окружающего нас мира. К сложным сетям относятся сети социальных и экономических связей, сети трафика транспорта, энергии, информации и многое другое. Основная цель изучения сетей - разработка алгоритмов для управления, оптимизации и предсказания процессов в сетях.
Однако, как давно было признано, многие сети являются существенно взвешенными, их ребра имеют различную силу. В социальных сетях между людьми могут быть более сильные или более слабые социальные связи. В сети метаболизма может быть больший или меньший поток вдоль частных путей реакции. В пищевых сетях может быть больший или меньший энергетический или углеродный поток между парами жертва-хищника. Весам ребер в сетях уделяется в физической литературе относительно небольшое внимание по той исключительной причине, что в любой области рекомендуется рассмотреть сначала простые случаи (невзвешенные сети) и только потом перейти к более сложным (взвешенные сети). С другой стороны, есть много случаев, когда веса ребер сети известны, и игнорировать их - значит отбросить много данных, которые, по меньшей мере теоретически, могли бы помочь нам лучше понять эти системы.
Данная работа посвящена разработке программного обеспечения для анализа и моделирования взвешенных сетей.
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 - число вершин), элемент которой равен весу ребра , если таковое имеется в сети; в противном случае элемент полагается равным нулю или бесконечности в зависимо?/p>