Главная / Учебные материалы / ЛЕКЦИОННЫЕ МАТЕРИАЛЫ / Лекция 4. Методы исследования и моделирования комплексных сетей / Введение в методы исследования и моделирования комплексных сетей

Введение в методы исследования и моделирования комплексных сетей

Для описания процессов социодинамики в связных сообществах применяются различные математические формализмы: графовые модели [1], уравнения популяционной динамики [2], мультиагентные системы [3] и пр. Однако наиболее теоретически обоснованным является формализм комплексных сетей.

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

Каждое состояние комплексной сети представляется взвешенным неориентированным графом G, который определяется как совокупность (V. E) конечного множества вершин V, dim(v)=N, и множества ребер E, состоящего из неупорядоченных пар (u, v), где и . Каждая вершина характеризуется своей степенью, т.е. числом инцидентных ей ребер.

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

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

1.– пространство элементарных событий. Пусть V_i – множество всех вершин веса (типа) i , возможно бесконечное, а E_i,k – множество всевозможных графов-звеньев, инцидентных паре вершин, одна из которых имеет вес i, а другая вес k:



2.– сигма алгебра подмножеств . Любой граф, содержащий вершины весов i = 1,...N₁ может быть составлен из элементов множества и соответственно рассмотрен как подмножество множества .

3. – сигма-аддитивная мера на множестве (вероятностная мера) – отражает вероятностные закономерности формирования топологии комплексной сети. – вероятность того, что из всех возможных графов (элементов) комплексная сеть изображается графом G.

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

Использование вероятностного подхода позволяет изучать комплексные сети посредством аппарата статистической физики [9, 10]. В настоящее время существует большое число различных подходов к описанию и моделированию комплексных сетей, использующих инструменты статистической физики [11–17]. Комплексные сети содержат огромное количество элементов и имеют сложную структуру, что и обусловливает эффективность вероятностного подхода к сети как совокупности микросостояний. В частности, оказывается эффективным непосредственное применение к комплексным сетям конструкций статистической физики [17–22] (статистические ансамбли, статистические суммы, средние по ансамблю и т.д.) Достоинством такого подхода является возможность дать описание в рамках единого формализма для различных классов моделей комплексных сетей, включая случайные графы (модели Эрдоша-Реньи [22, 23]), модели скрытых переменных [16, 24] и их обобщения [17, 20].

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