Повна версія

Головна arrow Інформатика arrow Моделирование сложных сетей

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Масштабно-инвариантные сети

Функция распределения степени узлов Pk для масштабно-инвариантной сети (Scale-Free - SF) имеет вид:

Такое распределение хорошо известно в теории вероятности как распределение Парето. Обычно для реальних сетей показатель у лежит в пределах от 2 до 3.

В том случае, когда к можно считать непрерывной переменной, обозначим ее - х (х > 0 ) необходимо учесть, что во всех реальных случаях существует минимальное значение

этой переменной -

Нормировочная константа C для непрерывного случая определяется, при этом, из условия

и равна

откуда ясно, что распределение (1.31) имеет смысл только при у> 1.

Дополнительное ограничение у > 2 на показатель накладывает требование иметь конечное среднее значение -

а для существования т -ного момента

требуется выполнения условия у > 1 + т.

С распределением (1.2.5) связано так называемое правило 80/20, в шуточном варианте - "20% людей выпивает 80% пива", и предполагается, что такого рода соотношение имеет место для многих других родов деятельности человека.

В самом деле, доля узлов 5(х) имеющих значение степени, больших х, составляет:

Эти узлы в сумме содержат долю Ш(х) от всех связей

Из (1.2.В) и (1.2.9) сразу же следует

На рис. 1.2.1 приведена зависимость W от 5 для различных значений у. Очевидно, чем больше значение показателя у, тем зависимость W =W (5 ) ближе к линейной.

При показателе у= 2.161 для 5 = 0,2 значение W = 0.8 соответствует правилу Парето (80/20). Чем больше значение показателя у, тем зависимость W =W(5) ближе к линейной.

Зависимость W = W( 5)

Рис. 1.2.1 - Зависимость W = W( 5)

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

При показателе γ= 2.161 для s = 0,2 значение W = 0.8 соответствует правилу Парето (80/20). Чем больше значение показателя у, тем зависимость W = W(5) ближе к линейной.

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

С одной стороны:

с другой стороны, доля их богатства W(хм) = 1/2 , т.е.

Подставляя значения хм из (1.2.11) в (1.2.12) находим

т.е. для значения показателя у= 2.161 половиной всех денег владеет меньше 1% (0.67%) людей.

Назовем этих людей "богатыми". Безмасштабность означает, что среди "богатых распределение на "богатых" и "бедных" в точности такое же. Т.е., как легко подсчитать, что 0.67% среди "богатых" владеют половиной всего "богатства" "богатых" (т.е. 1/4 от всего богатства).

Для любого значения b для безмасштабного распределения

т.е. измените масштаба (х →bх) приводит только к умножению распределения на константу.

Еще один, часто приводимый, пример для БР распределения связан с "компьютерной жизнью". Если в РС файлы размера 2 КВ составляют четверть от файлов размером 1 КВ, то число файлов размером 2 МВ будет составлять четверть от числа файлов размером в 4 МВ.

В дискретном варианте нормировано немного сложнее:

SF распределение

где

функция Римана.

Таким образом, согласно (1.2.15):

Dorogovtsev, A.V. Goltsev, J.F.F. Mendes. Critical phenomena in complex networks, arXiv:0705.0010.

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

а

равна

Сеть (граф) со SF распределением степени узлов может быть как случайной, так и детерминированной. Существует много "игрушечных" примеров детерминированных сетей со

SF распределением, например, так называемые (и, у) –цветы и (и,у)-деревья. Построение (и,у)-цветка начинается с цепочки ш = и + у связей, после чего, на каждом следующем шаге, каждая связь заменяется на цепочку из двух частей и и у, как показано на рис. 5.

На рис. 1.2.2 показано несколько шагов построения (1,2), (1,3), и (2,2) цветов.

На п-ом шаге построения число связей в такой сети

В тоже время число узлов на п -м шаге - Nn подчиняется следующему итерационному соотношению

откуда

Примере построения (и, v) -цветов: а - (1,2)-цветок; б - (1,3)-цветок; в - (2,2)-цветок: 0 - узлы, появляющиеся на данном шаге построения; • -

Рис. 1.2.2 - Примере построения (и, v) -цветов: а - (1,2)-цветок; б - (1,3)-цветок; в - (2,2)-цветок: 0 - узлы, появляющиеся на данном шаге построения; • - "старые узлы"; жирные линии - связи, появляющиеся на данном шаге построения.

Согласно правилу построения (u,v) -цветов, на п-ом шаге встречаются узлы только со степенями

обозначая Nп - число узлов на шаге п со степенью 2Ш можно записать следующее итеративное соотношение:

Откуда:

Так как при

из

И следует, что

где

И, таким образом, (u, у) -цветы действительно является SF-сетями.

Для сети с

имеются узлы с максимальным значением степени -

Значение

, конечно, зависит от полного числа узлов - N. Эта зависимость степенная и следующим образом зависит от показателя у:

Коэффициент кластеризации для БР для случайного графа определяется из

где для у< 3 имеем

и, таким образом:

 
<<   ЗМІСТ   >>