ФОРМАЛИЗМ КОМПЛЕКСНЫХ СЕТЕЙ


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

Формализм комплексных сетей применим для описания различных многосвязных систем реального мира. Примерами комплексных сетей служат социальные сети (знакомств, соавторства ученых), информационные (цитирования в научных статьях, ссылок WWW), технологические (Интернет как сеть компьютеров, транспортные и электрические сети) и биологические (сети нейронов в мозге, взаимодействующих протеинов, генетические сети).

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

  1. ‑ пространство элементарных событий. Пусть ‑ множество всех вершин веса (типа) , возможно бесконечное, а ‑ множество всевозможных графов-звеньев инцидентных паре вершин, одна из которых имеет вес , а другая вес : , тогда .
  2. ‑ сигма алгебра подмножеств . Любой граф, содержащий вершины весов может быть составлен из элементов множества и соответственно рассмотрен как подмножество множества .
  3. ‑ сигма-аддитивная мера на множестве (вероятностная мера) отражает вероятностные закономерности формирования топологии комплексной сети. ‑ вероятность того, что из всех возможных графов (элементов ) комплексная сеть изображается графом G.

Использование формального описания вероятностного пространства позволяет описывать динамические процессы на сетях даже в тех случаях, когда число узлов графа является ограниченным (т.е. отсутствует достаточно большая наблюдаемая выборка).

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

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

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

  • Модель случайного графа. Простейшим примером такой сети является сеть, в которой фиксировано число вершин n и ребер m. Из всего множества пар вершин равномерно и случайно выбирается m пар и между ними проводится ребро. Для случайного графа распределение степеней вершин является пуассоновым.
  • Конфигурационная модель. Конфигурационная модель, в отличие от случайного графа, позволяет построить сеть с заданным законом распределения степеней.
  • Модель малого мира. Отдельный класс сетей, основанный на построении связей между ближайшими соседями.
  • Модель предпочтительного добавления (preferential attachment). Данная модель позволяет строить сети со степенным распределением; при этом его характеристики зависят от степени роста сети.

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

,

.

Эволюционный оператор может быть представлен как композиция нескольких различных операторов

,

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



вернуться назад