< Попер   ЗМІСТ   Наст >

Модели артефактных сетей

Сети Эрдеша-Реньи

Сеть (граф) Эрдеша-Реньи (Е1К-сеть) это такая сеть, когда каждая пара узлов соединена с вероятностью р . В пределе большого числа узлов N функция распределения степеней узлов имеет вид:

В пределе N →∞ значение в построенной таким образом Е1К сети определено однозначно. В реальном случае для конечного значения числа узлов следует различать две модели Е1К сети - модель Гильберта (0пр -модель) и собственно модель Эрдеша-Реньи (Спт). В модели Спт фиксируется вероятность р. Для сети с конечным значением узлов N это означает, что = pN, при этом число связей М определено только в среднем (М^ = pN(N — 1) /2 . В модели Гильберта Опр задана не вероятность р, а число связей М, теперь вероятность р определена как = pN( N — 1) /2 , а средняя степень узла равна ^к) = 2М / N. Различие между этими моделями аналогично различию между каноническим и микроканоническим ансамблями в статистической физике. В микроканоническом ансамбле задана энергия системы, а в каноническом температура, при этом энергия флуктуирует вокруг среднего значения.

В пределе N →∞ , р → 0 , pN - конечное число не равное нулю, оба определения сети Эрдеша-Реньи и Гильберта совпадают.

Сеть Эрдеша-Реньи является "хорошо соединенной" -среднее минимальное расстояние между узлами порядка 1п N << N (N >> 1). Среднее минимальное расстояние между узлами легко оценить из следующих соображений. У каждого соседа есть еще в среднем по соседей, к каждому из

которых можно дойти за два шага. За 1 шагов можно в среднем дойти до (к) узлов.

Тогда для среднего минимального расстояния 1 между узлами сети из N узлов получаем:

Для сети ЕЯ: 1 ~1п N

Очень небольшое (логарифмически малое по сравнению с числом узлов) значение минимального расстояния, делает случайную ЕК-сеть так называемым "малым миром". Для

каждого узла сети, состоящей, например, из N = 109 узлов (порядок числа людей на Земле) со средним числом связей {к} = 100 (приблизительно столько людей мы лично знаем)

минимальное среднее расстояние равно

т.е. не более пяти шагов.

Заметим, что для регулярной сети, например, для квадратной решетки это расстояние значительно больше

для приведенного примера

Критическое значение рс, при котором в сети рождается гигантский кластер сразу же находится из критерия Моллоя-Рида

Так как

, то для pc получаем:

 
< Попер   ЗМІСТ   Наст >