1.2.3 Модель графа Эрдеша-Реньи

В теории графов модель Эрдеша – Реньи представляет собой модель для генерации случайного графа с постоянной вероятностью появления ребра между двумя вершинами независимо от других ребер. Согласно данной модели, граф конструируется с помощью соединения пар вершин случайным образом. Каждое ребро включается в граф с вероятностью p независимо для каждой пары вершин. С ростом p от 0 до 1 граф становится все более насыщенным ребрами. При p = 0 имеем пустой граф (граф, не имеющий ребер), при p = 1 – полносвязный граф. При фиксированном количестве вершин в графе вероятность p – единственный входной параметр модели Эрдеша – Реньи.

Простота модели Эрдеша – Реньи случайного графа позволяет получать различные аналитические оценки. Однако стоит отметить, что модель в среднем не воспроизводит такие типичные свойства реальных сетей, как степень вершин, величина коэффициента кластеризации и длины пути. [5]

5. 1.3 Модель графа с нппс

Случайные графы с НППС были впервые предложены В.Н. Задорожным в 2010 году в статье [6]. Данные графы генерируются на основе правила «предпочтительного связывания» (богатый становится богаче). Граф с НППС выращивается из графа-затравки итерационно, путём добавления вершин со случайным числом рёбер r, с заданной функцией предпочтения f ≥0, зависящей от степени связности k_i вершины. Вероятность p_i присоединения свободным концом нового ребра к уже существующей вершине графа зависит от функции предпочтения и вычисляется по формуле (2):

. (2)

Модели графов с НППС в последнее время получили широкое развитие. В работе [7] были найдены эффективные способы генерации графа. В [6, 8] представлены такие способы калибровки графов, которые позволяют при заданном распределении вероятностей r, путём подбора функции предпочтения f(k) генерировать граф с требуемым распределением степени связности вершин.

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

6. 1.4 Обзор аналогов

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

Рассматриваются алгоритм генерации графа БА и ускоренный метод генерации графа с НППС, а также метод сепарабельной реконфигурации. Представляются графики распределения степени связности графов. Описываются результаты сравнений различных характеристик реальных сетей и графовых моделей.

1. 1.4.1 Ускоренный метод генерации графа ба и графа с нппс

Алгоритм данного метода был представлен в [9].

Граф БА генерируется из небольшого графа-затравки путём добавления новых вершин с фиксированным числом рёбер m ≥ 1. Свободный конец нового ребра присоединяется в соответствии с формулой (3):

, j = 1,…, N, (3)

где N – текущее число вершин в графе.

Из формулы видно, что чем больше степень связности у вершины, тем выше вероятность её выбора.

На рисунке 2 представлена блок схема этого алгоритма.

Рисунок 2 – Схема алгоритма генерации графа БА [9]

Выбор вершин для присоединения может быть выполнен на основе стандартного подхода разыгрывания дискретной случайной величины (ДСВ). Данный подход можно описать так. Пусть задана некоторая система непересекающихся событий {А₁, … , А_n}, заключающихся в выборе очередной вершины (всего в графе n вершин). Вероятности выбора вершин события {А₁, …, А_n} равны соответственно p₁, … , p_n, (p₁ + p₂ + … + p_n = 1). При построении алгоритма отрезок [0,1) необходимо разбить на n интервалов длиной p₁, … , p_n, и отслеживать попадание сгенерированного значения большой случайной величины (БСВ) z в соответствующий интервал. Программная реализация данного алгоритма в [10] была названа БА_ДСВ (m, N, G).

В генератор БА_ДСВ (m, N, G) передаётся параметр m, определяющий число рёбер, добавляемых на каждом шаге, и число вершин N в генерируемом графе. При генерации передаётся также граф-затравка G, содержащий M вершин (M ≤ N).

На каждом шаге генерации добавляется новая вершина v_i (M ≤ i < N) c m рёбрами. Добавления m рёбер являются независимыми событиями, поэтому каждая следующая выбранная для присоединения вершина добавляется в специальный список lst, пока не будут выбраны все m вершин. После выбора всех m вершин (выход из цикла) в граф G «одновременно» добавляются m новых рёбер e = (v_i, v_lst[h]), между добавленной вершиной v_i и вершинами из списка v_lst[h] (p = 1, … , m). Далее список lst очищается, и алгоритм переходит к очередному шагу добавления новой вершины, пока не будут добавлены все (N – M) вершин.

Основная трудоёмкость рассмотренного алгоритма заключается в количестве итераций при выборе вершины для присоединения, поскольку в исследуемых сетях таких вершин сотни тысяч. Среднее число итераций при выборе вершин в графе, содержащем n вершин при условии, что степени вершин при их переборе распределены случайно, равно n / 2 [10].

Данный алгоритм можно ускорить, если разбить всё его множество вершин на отдельные слои. Слой – это подмножество вершин, которые имеют одинаковую степень связности.

После того, как всё множество вершин разбито на слои, происходит выбор новой вершины для присоединения. Сначала случайным образом выбирается номер слоя, а затем из этого слоя равновероятно выбирается вершина.

Схема данного алгоритма представлена на рисунке 3.

Рисунок 3 – Схема алгоритма ускоренного метода генерации графа БА и графа с НППС [10]

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

Генерация графа БА размером 100 тыс. вершин базовым алгоритмом занимает около трёх часов.

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

Рисунок 4 – РСС (слева на право: РСС калиброванного графа и сети автономных систем интернет; РСС калиброванного графа и сети маршрутизаторов интернет; РСС калиброванного графа и сети участия актёров в общих фильмах) [6]

Первый график на рисунке 4 характеризует качество идентификации сети автономных систем интернет по данным [11] (число узлов и рёбер равны соответственно N = 22963, R = 48436).

Второй график на данном рисунке характеризует качество идентификации сети маршрутизаторов интернет по данным [12] (N = 124651, R = 207214). Параметры генератора: ,,,,,.

Последний график характеризует идентификацию сети участия актеров в общих фильмах [13] (N = 511416 – без изолированных узлов, R = 1463331). Два соответствующих актерам узла связаны ребром, если эти актеры снимались в одном фильме. Здесь , численно фиксированы, и приk > 10 общая формула весов имеет вид .

Однако соответствие по РСС сети и ее модели не означает, что эти структуру соответствуют по другим структурным характеристикам, а модель является адекватной. Так на IV региональной научно-практической конференции был представлен доклад [14], в котором особое внимание уделялось исследованию диаметра сл.г. В данной работе был проведён следующий эксперимент. Было выбрано 7 реальных сетей с уже известными параметрами. Для каждой из этих сетей было построено несколько различных модели сл.г. и подсчитан диаметр, как реальной сети, так и моделей. Длина выборки равнялась 10. Результаты этого эксперимента представлены в таблице 1.

Таблица 1 – Сравнение диаметра у реальных сетей и их моделей

Имя сети	Вершины	Рёбра	Диаметр сети	БА				Граф Эрдеша-Реньи				Граф Уаттса-Строгатца			НППС
				max	min	ср.	max		min	ср.	p=0		p=1
USAir97	332	2126	6	5	9	7	6		7	7	24		4	5
PGPgiantcomp	10680	24340	24	11	15	13	29		32	31	2470		14	8
P2p-Gnutella31	62586	147892	31	14	19	16	38		40	39	15647		16	9
Oregon2_01052	11461	32731	9	12	15	13	18		22	19	1910		10	7
My_polBlog	1491	19089	9	8	12	10	5		5	5	58		4	8
myAs	22963	48436	11	13	15	14	31		6	3	741		15	5
Email-Enron	36692	367662	13	15	17	16	8		8	8	1835		5	10

Из этой таблицы видно, что среднее значение диаметра графа БА практически совпадает только в двух случаях, в двух других случаях диаметр графа БА меньше диаметра реальной сети почти в два раза. В модели графа Эрдеша-Реньи для сети автономных систем диаметр модели меньше почти в четыре раза. Диаметр графа в моделях Уаттса-Строгантца при p = 0 имеет чрезмерно большое значение и совершенно не соответствует диаметру реальных сетей. Что касается графа с НППС, то тут значения диаметра в целом получаются значительно меньше.

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

В работе [15] производится исследование соответствия графовых моделей и их сетей на количество подграфов в виде квадрата. Квадратом назван подграф из четырёх вершин и четырёх рёбер, связанных в кольцо.

Данные, полученные в [15], показывают, что при одинаковом числе узлов N и ребер E, число квадратов в графах БА, конфигурационных графах, графах с НППС оказывается значительно меньше, чем в реальных сетях. Эти данные представлены ниже в таблице 2.

Конфигурационная модель генерации графа БА описана в [30]. Её можно представить следующим образом.

Пусть дано распределение P_k степени связностиNвершин.

1. Помечаем степенями связности k_iвсеNвершинMap<v_i,k_i> (i= 1, N).

2. Рисуем «хвосты рёбер» в соответствии с полученными числами k_i.

3. Распределяем «хвосты ребер» на пары случайно равновероятно, формируя ребра между вершинами.

Таблица 2 – Число квадратов в реальных сетях (n_□реал), в графе БА (n_{□графБА}), в конфигурационной модели (n_{□конф.м.}), в графе с НППС (n_{□графНППС})

Название сети	Характеристики сетей				Теоретические величины
	N	E	n□реал	m		n□графБА	n□конф.м.	n□графНППС
Сеть маршрутизаторов	124651	207217	562687	2		2285	10107	33030
Сеть пользователей программы PGP	10680	24340	1010957	3		1070	9252	19191
Сеть автономных систем Интернет	22963	48436	3088900	2		1179	3860	21361
Сеть адресов электронной почты	36692	183831	36262047	5		61950	353547	997506

Из таблицы 2 видно, что модель графа БА содержит наименьшее число квадратов и наиболее сильно отличается от числа квадратов в реальных сетях. Число квадратов в конфигурационной модели в разы больше, но всё же достаточно. Наибольшим числом квадратов обладает граф с НППС, однако их всё равно на порядки меньше, чем в реальных сетях.

С помощью программы предложенной в [16] не трудно рассчитать значения коэффициента кластеризации в сетях и их графовых моделях. Так в таблице 3 приводятся данные расчёта коэффициента кластеризации сети автономных систем интернет и её моделей. Графа БА сгенерирован с параметров средней степени связности m = 2. Граф с НППС был откалиброванным по заданному эмпирическому РСС. Количество вершин в данных моделях случайных графов соответствует числу узлов в реальной сети автономных систем: 22963 узла.

Таблица 3 ‑ Расчеты коэффициента кластеризации в различных сетях

Имя сети	Значение коэффициента кластеризации
Сеть автономных систем	0.01124
Граф БА	0,00063
Граф с НППС	0.00502

Из таблицы 3 можно увидеть, что значение коэффициента кластеризации в модели графа БА отличается от значения коэффициента кластеризации в реальной сети на несколько порядков. Граф, сгенерированный в соответствии с НППС, имеет намного большее значение коэффициента кластеризации. Однако, несмотря на то, что значение параметра значительно увеличилось, оно всё равно отличается от значения этого же параметра в реальной сети более чем в два раза.

В работе [10] приведены данные об исследовании других реальных сетей и сравнении их с моделью графа БА по коэффициенту кластеризации. Также было установлено, что в реальных сетях эта структурная характеристика на порядки больше её показателя в графах БА. Результаты данного исследования представлены в таблице 4.

Таблица 4 – Коэффициент кластеризации в реальных сетях (С_∆реал) и в графе БА (С_{∆графБАтеор}) [10]

Название сети	Характеристики сетей				Теоретические величины			С∆реал / С∆графБАтеор
	N	E	С∆реал	m		С∆графБАтеор 00
Сеть маршрутизаторов	124651	207217	0,03863	2		0,00185	20,86609994
Сеть пользователей программы PGP	10680	24340	0,37802	3		0,00232	163,0688118
Сеть автономных систем Интернет	22963	48436	0,01146	2		0,00076	14,93567203
Сеть адресов электронной почты	36692	367662	0,08531	10		0,00342	24,9348154
Сеть ссылок веб-страниц (GOOGLE)	875713	5105039	0,05523	5		0,00011	503,4293618
Сеть товаров интернет-магазина Amazon	262111	1234877	0,23608	4		0,00024	1001,232022

По таблице 4 видно, что хотя модель графа БА выращивалась для того же количества вершин N и с тем же параметром средней степени связности m значения коэффициента кластеризации в графе БА в некоторых случаях меньше на несколько порядков.