Материал: Теория сетевых войн. Живучесть атакуемых сетей. учеб. пособие. Остапенко А.Г., Калашников А.О

Через |A| обозначена мощность множества A (количество

элементов в нем),а 2A–это совокупность всех подмножеств множестваA.

Элемент сигма-алгебры Fn–это набор графов. Если нам хочется найти вероятность, с которой граф на n вершинах обладает данным свойством A, то мы просто берем множество A Fn, состоящее из всех графов, для которых выполнено свойство A, и вычисляем:

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

Сделаем еще ряд полезных замечаний. Во-первых, если p=

1/2, то, как видно из формулы (2.2), вероятность любого графа равна 2–Cn^2. Иными словами, в этом специальном случае все

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

В действительности, мы не только не обязаны предполагать, что p=1/2 (хотя и этот случай очень важен),мы даже можем считать, что с ростом величины n(числа вершин) вероятность p возникновения ребра изменяется. Иначе говоря, p=p(n)–любая функция, значения которой заключены между нулем и единицей. Как правило, в науке о случайных графах важны даже не сами вероятности событий, но их предельные значения.

Свойство выполнено почти всегда, если его вероятность стремится к единице при n→∞.

31

Представим некоторые обобщения модели Эрдеша – Реньи. Пусть Vn = {1, . . . , n}. Вероятность ребра между вершинами i и j мы обозначим через pij. В формате аксиоматики Колмогорова мы получаем вероятностное пространство

в котором Ωn = {G = (Vn, E)}, Fn = 2Ωn, P , , (G) =

∏( , ) p , ∏( , ) (1 −p , ).

Важный частный случай описанного пространства получается, коль скоро мы фиксируем некоторый граф Hn = (Vn, En) и полагаем

Иначе говоря, ребра графа Hn возникают в случайном графе независимо друг от друга с одной и той же вероятностью p = p(n) [0, 1], а ребра, которых в графе Hn нет, не возникают в случайном графе вовсе. Этот вариант модели принято обозначать G(Hn, p). В ней

Ясно, что модель G(Hn, p) и есть та самая модель, которая вполне адекватна вопросу о надежности транспортной сети.

2) Модель графа Барабаши – Альберт (граф БА)

представляет собой алгоритм генерации случайных безмасштабных сетей с использованием принципа предпочтительного присоединения[23].

Многие исследуемые сети попадают под класс безмасштабных сетей. Это значит, что они имеют степенное распределение по степени узла, тогда как модели случайных

32

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

-рост сети -принцип предпочтительного присоединения (ПП).

Обе концепции широко представлены в сетях реального мира. Рост значит, что число узлов сети увеличивается со временем.

Принцип предпочтительного присоединения заключается в том, что чем больше связей имеет узел, тем более предпочтительно для него создание новых связей. Узлы с наибольшей степенью имеют больше возможностей забирать себе связи, добавляемые в сеть. Интуитивно, принцип предпочтительно присоединения может быть понят, если мы думаем в терминах социальных сетей, которые объединяют людей. Здесь связь от А к B значит, что человек A «знает» или «знаком» с человеком B. Сильно связанные узлы представлены известными людьми с большим числом связей. Когда новичок попадает в сообщество, для него/неё более предпочтительно связаться с одним из известных людей, чем с относительно неизвестным. Подобным образом во всемирной сети страницы связываются с хабами, к примеру, с хорошо известными сайтами, как Гугл или Википедия, чем со страницами, которые мало кому известны. Если выбирать для связи новую страницу случайным образом, то вероятность выбора определённой страницы будет пропорциональна её степени. Это объясняет принцип предпочтительного присоединения.

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

33

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

Каждая новая вершина присоединяется к уже существующим вершинам с вероятностью пропорциональной степени связности этих вершин. Вероятность pi того, что вершина присоединится к i-ой вершине равна:

где ki–степень i-ой вершины.

3) Модель графа Уаттса – Строгатца[23].

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

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

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

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

34

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

Чтобы построить сеть «малого мира», следует начать с регулярной циклической решётки с N вершинами, каждая из которых соединена с k ближайшими соседями в каждом направлении. Для каждой вершины задаётся 2k связей, где N >> log2(N) >>1. Затем каждое ребро присоединяется к случайной паре вершин с вероятностью p.

При условии p=0 получается упорядоченная решётка с большим количеством циклов и большими расстояниями, а при условии p→ 1 сеть становится случайным графом с короткими расстояниями, и малым количеством циклов.

Данная сеть может иметь три состояния:

−регулярная сеть, каждый узёл которой соединён с четырьмя соседними;

−та же сеть, у которой некоторые «ближние» связи случайным образом заменены более «дальними» (именно в этом случае возникает феномен «малого мира»);

−случайная сеть, в которой количество подобных замен превысило некоторый установленный порог.

На (рис. 2.8.) представлена иллюстрация данной модели.

Рис. 2.8. Модель графа Уаттса-Строгатса

35