Предельное поведение числа ребер случайного конфигурационного графа вблизи критических точек

Труды Карельского научного центра РАН №10. 2015. С. 114-122 DOI: 10.17076/mat144

УДК 519.175.4

ПРЕДЕЛЬНОЕ ПОВЕДЕНИЕ ЧИСЛА РЕБЕР СЛУЧАЙНОГО КОНФИГУРАЦИОННОГО ГРАФА ВБЛИЗИ КРИТИЧЕСКИХ ТОЧЕК

Ю. Л. Павлов1, Е. В. Феклистова1

1 Институт прикладных математических исследований Карельского научного центра РАН

Рассматривается случайный конфигурационный граф с N вершинами, степени которых независимы и одинаково распределены по степенному закону с параметром т = т(N). Свойства этого графа зависят от значения параметра т. Эти значения можно разбить на три области: т > 2, т G (1, 2), т < 1, в каждой из которых структура графа сходна при всех значениях т, но резко отличается от структуры в двух других областях. Это значит, что значения т = 2 и т =1 являются критическими точками. Важнейшей характеристикой графа является число ребер. Его предельные распределения при N ^ то и фиксированных т также различны в указанных трех областях. Поэтому актуальным является исследование поведения числа ребер в переходных ситуациях при т, изменяющихся в окрестностях критических точек. В статье найдены локальные предельные распределения числа ребер графа при т ^ 2, т ^ 1, а также при т ^ то.

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

Yu. L. Pavlov, E. V. Feklistova. LIMIT BEHAVIOUR OF THE NUMBER OF EDGES IN A CONFIGURATION RANDOM GRAPH NEAR CRITICAL POINTS

We consider a configuration random graph with N vertices, whose degrees are independent and identically distributed according to power-law distribution with the parameter т = т(N). The properties of this graph depend on the value of the parameter т. These values can be grouped into three zones: т > 2, т G (1, 2), т < 1, in each of which the structure of the graph is similar for all values of т, but differs greatly from the structure in the other two zones. This means that the values т = 2 and т = 1 are critical points. The most important characteristic of a graph is the number of edges. Limit distributions of this characteristic also differ between these three zones as N ^ то and т is fixed. It is therefore important to study the behavior of the number of edges in transitional situations when т changes in the neighborhood of the critical points. In this paper the local limit distributions of the number of edges of a graph as т ^ 2, т ^ 1, and also as т ^ то were obtained.

Key words: configuration random graph, number of edges, local limit theorems, critical points.

Введение

Конфигурационные графы со случайными степенями вершин в последние десятилетия широко используются для моделирования сложных сетей коммуникаций, таких, как Интернет, системы мобильной связи и т. д. (см., например, [5, 8]). Кроме того, недавно предложено использовать такие графы для описания динамики развития лесных пожаров и банковских кризисов [1, 3]. Конфигурационные графы конструируются в два этапа. На первом этапе определяются степени всех вершин, которые рассматриваются как независимые одинаково распределенные случайные величины. Степень каждой вершины равна числу выходящих из нее «полуребер», т. е. ребер, инцидентных данной вершине, но для которых смежные вершины еще не определены. В рассматриваемых моделях считается, что все полуребра графа, как и вершины, различны (занумерованы). На втором этапе построения графа полуребра случайным образом попарно соединяются для образования ребер, при этом для большинства сетей достаточно предположить, что такие соединения происходят равновероятно.

Пусть N означает общее число вершин в графе, а £ь£2, ...,£м - случайные величины, равные степеням вершин 1,..., N соответственно. Обозначим

Рк = Р{& = к}, к = 1,2,..., г = 1,..., N.

Многочисленные наблюдения за реальными сетями показали, что для больших значений к число узлов, имеющих к связей, пропорционально к-(т+1), где т - положительный параметр, в большинстве случаев принадлежащий интервалу (1, 2) [6, 8, 10]. Это значит, что при к ^ те мы можем считать, что

- й(к)/кт+1,

Рк

Р{£ ^ к} = кТ,г = 1,

N

или, что эквивалентно,

Рк = к-т - (к + 1)-Т,к = 1,2,.. Легко проверить, что при к ^ те

Рк

тк-

и, следовательно, условие (2) выполнено. Заметим еще, что при т ^ 1

= С (т ) = Е к-

к=1

где ((т) - значение дзета-функции Римана в точке т,

= а2 = 2

а при т ^ 1 сумма ряда (6) равна бесконечности.

Обозначим (м сумму степеней всех вершин графа. Поскольку такая сумма должна быть четным числом, в противном случае в граф вводится вспомогательная дополнительная вершина единичной степени. Ясно, что введение такой вершины не влияет на асимптотическое поведение графа. Таким образом, ("м = £1 +    + в случае четной суммы степеней и ("м = £1+  + 1 иначе. Далее полуребра равновероятно соединяются, формируя ребра. Ниже рассматривается предельное поведение (м при N ^ те, которое очевидным образом определяет асимптотику числа ребер графа, которое равно /2.

В статье [11] получены локальные предельные теоремы для (м при N ^ те и всех возможных фиксированных значений т. Справедливы следующие результаты.

Теорема 1. Пусть N ^ те, т > 2. Тогда

вир

п

Р{(м = п}--= е

у2п

-> 0.

(2) Теорема 2. Пусть N ^ те,т = 2. Тогда

где Л,(к) - медленно меняющаяся функция. Проведенные исследования показали, что при больших N структура и динамика развития случайного графа практически полностью определяется свойством (2) и не зависит от вероятностей Рк для небольших значений к и от вида функции Л,(к). Это дает возможность выбора распределения степеней вершин (1) наиболее удобным для изучения графов способом.

Мы будем рассматривать модель случайного конфигурационного графа, предложенную в [10] и удовлетворяюшую перечисленным выше условиям. В этой модели предполагается, что

вир

п

\Z2nN 1п NР{(м = п} - е -мп

(п-М((г ))2 N

0.

Теорема 3. Пусть N ^ те, т € (1, 2). Тогда

вир

N1/тРК* = п}- )

^ 0,

где »(х) - плотность устойчивого распределения с параметром т и характеристической функцией

/

пт

х сов

2

(3) Г(х) - значение гамма-функции в точке х.

115

п

Теорема 4. Пусть N ^ ж, т = 1. Тогда вир ^Р{(м = п}- #((п - N 1пN)/N)| ^ 0,

п

где д(ж) - плотность устойчивого распределения с характеристической функцией

/(*) = ежр{-^ (1 +

Ж"

Теорема 5. Пусть N ^ ж, т € (0,1). Тогда

вир

п

N1/т Р{

^ 0,

а

1п N ^ ж;

а^N(1 - е-^2), ум 1п N

7;

Вм =

V (1 - ет/2),

_ Ж У^

У- I

Тогда

ум 1п N ^ 0; ум 1п N ^ -7;

ум 1п N ^ -ж.

вир

п

1 (п-«;(т))2

Вм Р{См = е

V 2п

Теорема 7. Пусть N ^ ж, т = 1 + ум, ум ^ 0. Тогда

вир

п

где

N 1/т Р((м = п}-

п - N5 ^) \ )

^ 0,

^) =N/Т

у2 - с

где д(ж) - плотность устойчивого распределения с параметром т и характеристической функцией (8).

Приведенные теоремы подтверждают известный факт (см. [10]), что свойства графа существенно зависят от значения параметра т распределения (4). В частности, эти значения можно разбить на три области: т > 2, т € (1, 2), т < 1, в каждой из которых структура графа сходна при всех значениях т, однако резко отличается от структуры в двух других областях. Таким образом, значения параметра т = 2 и т = 1 можно назвать критическими точками или точками фазового перехода. В связи с этим актуальной является задача исследования предельного поведения ("м в случаях, когда параметр т не фиксирован, а зависит от N и при N ^ ж сближается с критическими точками.

Основные результаты

Ниже доказаны локальные предельные теоремы для сумм ("м при т ^ 1 и при т ^ 2. Справедливы следующие результаты.

Теорема 6. Пусть N ^ ж, т = 2 + ум, ум ^ 0, 0 < 7 < ж, а последовательность Вм выбрана так, что

с - постоянная Эйлера (с = 0, 57721...), д(ж) - плотность устойчивого распределения с характеристической функцией (9).

Представляет интерес также предельное поведение распределения суммы ("м при т ^ ж.

Теорема 8. Пусть N т ^ ж так, что ^8Т ^ ж. Тогда

вир

п

1

V N Р{(м = п}--= е 2ст2 N

у2п

а

0.

Вспомогательные утверждения

Ниже будут получены леммы 1-3 о слабой сходимости распределений суммы ("м к соответствующим предельным законам, а затем с помощью этих лемм доказываются теоремы 68. Заметим еще, что в теореме 7 при выполнении условия ум 1пN ^ 7, -ж < 7 < ж, выражение ) имеет более простой вид:

5^) = N/Т/ум + ум2 + с(е7 - 1).

Это следует из (11), разложения Г(-ум) в окрестности нуля [2, 7]:

Г(-ум) = -ум1 - с + Е(ум),

где Е(ум) - степенной ряд такой, что Е(ум) = О (ум), а также из того, что дзета-функция Ри-мана при достаточно близких к единице значениях аргумента в имеет вид [2]:

где

С (в) = —Ц+ с + Р(в), в1

(в) = Е Чг-^ (в - 1)к,

к=1

7^ - постоянные Стирлинга.

Лемма 1. Пусть N ^ ж, т = 2+ум, ум ^ 0, а последовательности Вм определены в (10). Тогда

Р{(См - N((т))/Вм Ф(ж),

где Ф(ж) - функция распределения стандартного нормального закона.

Доказательство. Пусть означает характеристическую функцию случайной величины - NZ(т))/В*. Тогда по теореме непрерывности нам достаточно показать, что

лг itN((т) 2 .

^(щ) = (Щ/В*)е-^ е-*2/2,

где - характеристическая функция £1. Из (4) нетрудно получить, что

случаях, указанных в (10). Учитывая, что в рассматриваемых условиях Г(1 - у*) ^ 1, а также (7) и (13), получаем, что 1п^ -Щ2/2, откуда и вытекает (15). Лемма 1 доказана.

Обозначим (Щ) характеристическую функцию суммы - N5(N))/N1/т, где величина Б(^ определена в (11).

Лемма 2. Пусть N ^ те, т = 1+ум, ум ^ 0.

= 1 - Ф(ей, т, 1)(1 - ей), (16) Тогда ^ (Щ) ^ ехр{-п|Щ (1 + г^ 2 1п |Щ|) }.

где Ф(^,т, а) = ^ - трансцендентная ¿=0

функция Лерча [9]. Известно [2], что при достаточно малых Щ справедливо представление:

Ф

т -1

где

+ С(т - 1)гщ + Я(¿)),

Я(¿) = Е ^^(гЩ)к

к=2

к!

1 + ¿¿С

1 +--^---^о--Г

в

N

В2

+3

-г'1 - Ч^) + ЧвВм

х ехр{-г£^(т))/В* }.

2в2 2Вм

N

1п =

^2С 2

2В2 2Вм

М2 +

+

NГ(1 - у*) ¿2

Ум(1 + Ум) В*

Ум вм

2в2 2Вм

+ О

В" вм

Доказательство. Используя (12) и (13) получаем, что

с

+ (-У-1 - с + Е(у*)ЖГ х ехр{-гум^»п ¿)п/2}.

Отсюда и из (17) следует, что при достаточно малых Щ

Ф

здесь значения дзета-функции от аргумента, меньшего единицы, понимаются в смысле аналитического продолжения. Отсюда и из (16) следует, что при Щ ^ 0

р(*) =1 + г*С(т) - Щ2С(т - 1)+ Щ2С(т)/2 - Г(1 - т)(-гЩ)т + О(Щ3).

Поэтому при N ^ те и любом фиксированном

х(у-1 + с)+ £>(т) + Е (у*) +(-у—1 - с + Е(у*)ЖГ

те

X Е (-¿ум(«»п Щ)п/2)к/к! + С(т - 1)гЩ

к=1

+Я (Щ)] ,

где

ОД = Е (-¿Щ)к/к!

к=2

Раскрывая скобки в (21) из (16), нетрудно найти, что при Щ ^ 0

р

х Е (-¿у*(^п Щ)п/2)к/к! + Д(г),

к=1

Используя (13) и известное [4] соотношение Г(-1 - ум) = Г(1 - у*)/(ум(1 + ум)), из (19) находим, что

где для остаточного члена Е(Щ) справедливо соотношение:

1/т) = o(1/N).

Нетрудно видеть, что

Теперь мы можем рассмотреть отдельно предельное поведение выражения (20) во всех

Е (-¿ум(¿»п Щ)п/2)к/к! = -(в»п Щ)г к=1

те

X Е

«=1 те

- Е(пум/2)25/(2«)!

«=1

117

Заметим, что при фиксированных Ь N|Ь/N 1/т|1+У-

те

X Е(-1)*-1(пум/2)2б—1/(2в - 1)!

s=1

= njtj/2 + o(1),

но

те

x ^(nyN/2)2s/(2s)! = o(1).

s=1

Легко проверить справедливость следующих соотношений:

itN1-1/т(1 - |t/N1/т|yN) = it(NyN/т - 1) + o(1),

itN1-1/т(1 - |t|yN/N1/т)/yN = it(NyN/т/yN - y—2 + ln |t| + o(1)).

Собирая вместе (23)-(29) и учитывая (12) (13), (14), находим, что

ln

+ it

NyN/т

-y—2 - с] + o(1). Отсюда следует, что

N

t

N1/т

ежж -

itNS (N) "iV^ J

^- 2 1+42in j

поэтому, учитывая (6) и (7), из (31) находим, что для определенной в (15) характеристической функции случайной величины (См - ^(т))/(а\^) справедливо равенство:

^(t) =

1+

iZ(т)t

t

2

- + Z2(т>W

N

+ O

1

a3Nv/N

_itN(izL

е ctVn (

откуда следует утверждение леммы 2.

Лемма 3. Пусть N, т ^ ж,так, что N/8Т ^ ж. Тогда Р{((м(т))/(а^Ж) < ж} ^ Ф(ж).

Доказательство. Для характеристической функции случайной величины £1 при Ь ^ 0 справедливо разложение:

р(Ь)=1 + - Ь2(а2 + Е2£1)/2

+ 0

Из (4) нетрудно получить, что

Е£3 = 3С(т - 2) - 3С(т - 1)+ ((т),

Логарифмируя это выражение, легко получить соотношение (15), что и доказывает лемму 3.

Доказательства теорем

Доказательство теоремы 6. По формуле обращения

-1/2e-zN/2

= (2п)"^ exp{-itzN - t2/2} dt,

bn P{zN = n}

ттБд

1

2п

e-itZN (

-пБл

B

N

N

dt,

где ¿м = (п - ^м(т))/Вм и

(Ь) = р(Ь)ежр{-г*С (т)}.

Рассмотрим разность

Ем = 2п (ВмР{(м = п} - (2п)-1/2е-^2/2) .

Из (32) и (33) следует, что эту разность можно представить в виде суммы

Ем = 11 +12 +1з +14,

где

A

I1 = J e-itZN ((р* (t/BN))N - e"i2/2) dt, У exp{-itzN - t2/2} dt,

—A

I2 = -

I3 = J e~UZN (p* (t/BN))N dt,

4 = J e-itZN (p* (t/BN))N dt,

eBn

t

а положительные постоянные А и е будут выбраны позднее.

Легко видеть, что для доказательства теоремы достаточно убедиться, что Я* стремится к нулю при N ^ те.

Из леммы 1 видно, что 11 ^ 0. Для интеграла 12 справедлива оценка:

ы <

-*2/2 йЩ,

!*!>А

поэтому 12 можно сделать сколь угодно малым выбором достаточно большого А. Ясно, что

N < Вм I й*.

Известно, что для любого е > 0 при е ^ существует такое число С > 0, что |^>(Щ)| ^ е-с, поэтому

^ п

|^(Щ)|м йЩ < Вме-см (п - е).

-см/

Отсюда и из (7), (10), (13) нетрудно получить, что 14 ^ 0.

Нам осталось рассмотреть интеграл 13. Оценим этот интеграл отдельно для пяти случаев выбора В*, указанных в условиях теоремы. Представим 13 в виде суммы 13 =13 + 13', где области интегрирования слагаемых соответственно равны:

Б' = {Щ : А < |Щ| < }, 5'' = {Щ : < |Щ| < еВ*}, а границы в каждом случае задаются свои.

В первом случае Вм = ум 1п N ^

те, а = е-С>1/:№ал/^, здесь и далее символы С1, С2, . . . означают некоторые положительные постоянные.

Пусть Щ € Б'. Используя (7) и (13), нетрудно показать, что

а2 = 2у—1 + 2с - ((2) - С2(2),

поэтому

-Щ2/(а2у*) - -Щ2/2.

ехР -

И

Г(1 - ум) ¿2 ум(1 + ум) а2 V ал/ж

£ е^2/2,

№

где й < 1. Нетрудно показать, что первое, третье и последнее слагаемые в сумме (20) при В* = являются бесконечно малыми по

сравнению с Щ2, поэтому из (35) и (37) следует, что для некоторого С2 > 0

№(*)| <е-°2*2

и интеграл 13 можно сделать сколь угодно малым выбором достаточно большого А.

Для оценки 13' аналогичным образом можно найти асимптотику всех слагаемых в сумме (20) и получить, что

1п^(Щ) = (2 - 2с + С(2) + С2(2) + 21пи)Щ2у*/4,

где 0 < и ^ е, а в силу выбора е для некоторого С3 > 0

|^(Щ)| < е-Сз*2/^.

Учитывая (34) и условие у* 1п N ^ те, отсюда находим, что

|13'| < 2еа^е-2Сз^ ^ 0.

Рассмотрим второй случай, в котором ум 1п N ^ 7,0 < 7 < те,Вм = Вл/^, где В = а\/1 - е-^/2, а = у-1. Как раньше, из (20) следует равенство:

, Щ2С2

1п ^(Щ) = ——- +

+

2В2

Г(1 - ум) ум (1 + ум) В2

В2

2В2

и в

№

+

Используя (13) и (36), нетрудно получить, что при Щ € 5'

^2С(т - 1)+Г(1 - у*) Щ2

В2 ум (1 + ум) В2

гр т В

в2 у*

(1 - е-7/2),

Известно [2,7], что при ум ^ 0

Г

Кроме того, в области Б' справедливо неравенство: | - ¿ЩДау^)|№ < е-С1 < 1, поэтому из (36) выводим, что

а остальные слагаемые в (38) бесконечно малы по сравнению с (39). Отсюда и из (34), (38) следует, что

поэтому

1п^(Щ) - -е-*2/2,

те

|1'3| < 2 ! е-*2/4 йЩ

А

119

е

2

и, как обычно, этот интеграл оценивается выбором достаточно большого А.

Проводя рассуждения аналогично тому, как это было сделано в первом случае, находим, что при Ь € Б"

№(*)| < е-С4*2 и, поскольку |Ь| ^ у-1,

|I'3'| < 2 J e-C4t dí ^ 0. y-1

В третьем случае Bn = VN ln N, yN ln N ^ 0, Dn = ln N и из (20) следует, что

ln ^(í) =

t2Z2

+

2 ln N Г(1 - yN) í2

í2Z

ln N

yN (1 + yN) ln N\ VN ln N

ií

2 ln N

Vn

+ O

í3

л/Ñ ln3/2 N

Опять, используя (13) и (36) и оценивая каждое слагаемое в (40), приходим к неравенству:

те

|I'3| < 2 J e-t2/4 dí.

A

те

|!з! < 2 J

e-C51 dí ^ 0.

ln N

В четвертом случае ^м = у-1, а в пятом = е-Сб/у- (-2N/yм)1/т. Оценивание интеграла 1з в этих двух случаях проводится по той же схеме, как и в случаях 2 и 1 соответственно. Доказательство теоремы 6 завершено.

Доказательство теоремы 7. Обозначим ^м = (п - N51/т и =

^(¿)ежр{-(N)}. Как и при доказательстве теоремы 6, представим разность

Ем = 2п^ 1/тР{(м = п}- )) в виде суммы

A

где Ii = J (У* (í/NЛ N

-A

-exp{-2|í| ( 1 + iln |í|)}) dí,

I2 = -

J 4-iíVN - 2

а интегралы 1з и 14 аналогичны одноименным интегралам в доказательстве теоремы 6.

Из леммы 2 видно, что 11 ^ 0. Для 12 справедлива оценка

Ы < 2 J e-nt/2 dí,

поэтому 12 можно сделать сколь угодно малым выбором А. Ясно, что 14 оценивается так же, как и подобный интеграл в теореме 6.

Используя (20) и проводя рассуждения, подобные выводу соотношения (30), нетрудно получить, что в области интегрирования 1з

поэтому

Оценка 13' проводится аналогично предыдущим случаям и при этом учитывается условие |Ь| > 1п N и выбор е. Тогда

№(*)| < е-С5^ 1п м

те

A

а последнее выражение можно сделать сколь угодно малым выбором достаточно большого A. Теорема 7 доказана.

Доказательство теоремы 8. Используя (32) и (33) при Bn = ал/N, находим, что

2n(aV2nÑP{CN = n} - (2n)-1/2e-zN/2) = Ii +I2 +1з + I4,

где интегралы Ii - I4 имеют тот же смысл, что и при доказательстве теоремы 6. Из леммы 3 следует, что Ii ^ 0, а I2 можно оценить так же, как и в теореме 6.

Рассмотрим I4. Поскольку - 1 = cosí + i sin í - 1 из явного вида $(ert, t, 1) и (16) находим, что при t ^ ж и ea\/N ^ |í| ^ пал/N

N

í

a^N

1 + cos

VN

+ i sin

а

1

RN = Ii +12 +13 +14

x(1 + o(1))]

N

и

поэтому для некоторого положительного д < 1

)|м <дм.

Тогда

|141 < па^д* ^ 0.

Для оценки 13 воспользуемся опять (16), явным видом функции Лерча и разложением ег* по формуле Тэйлора в окрестности нуля. Тогда получаем, что

* ()Г <е_с'"

следовательно,

оо

|1з| < 2 J e-C7t2 dt,

A

что равносильно (41). Теорема доказана.

Работа выполнена при поддержке РФФИ, грант 13-01-00009.

ЛИТЕРАТУРА

1. Аннаков Б. Б. Банковский кризис и пожары в лесу - Что общего? // [Электронный ресурс]. URL: http://www.empatika.com/blog/agent_mo-deling_forest_fire. 2008

2. Бейтман Г., Эрдейи А. Высшие трансцендентные функции. Гипергеометрическая функция. Функции Лежандра. М.: Наука, 1965. 296 с.

3. Лери М. М., Павлов Ю. Л. Лесной пожар на случайном графе со сгораемыми ребрами // Учен. зап. Петрозаводского государственного университета. 2013. № 2 (131). С. 96-99.

4. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т. 2. СПб.: Лань, 2009. 800 с.

5. Durrett R. Random graph dynamics. Cambridge University Press. 2006. doi: 10.1017/CB09780511546594

6. Faloutsos C., Faloutsos P., Faloutsos M. On power-law relationship of the Internet topology // Computer communications Rev. 1999. Vol. 29. P. 251-262. doi: 10.1145/316194.316229

7. Flajolet P., Sedgewick R. Analytic combinatorics // Cambridge University Press. 2009. doi: 10.1017/CB09780511801655

8. Hofstad R. Random graphs and complex networks. Eindhoven university of technology. 2011. 363 p.

9. Laurinskas A., Garunksis R. The Lerch zeta-function. Dordrecht: Kluwer, 2002. 189 p.

10. Norros I., Reittu H. 0n the power-law random graph model of massive data networks // Performance Evaluation. 2004. Vol. 55, N 4. P. 3-23.

11. Pavlov Yu. L., Feklistova E. V. Limit distributions of the edge number in random configuration graph // European researcher. 2013. Vol. 48, N 5-1. P. 1097-1100.

Поступила в редакцию 03.04.2015

References

1. Annakov B. B. Bankovskii krizis i pozhary v lesu - Chto obshchego? [Bank crisis and forest fire: What's in common?] [Elektronnyi resurs]. URL: http://www.empatika.com/blog/agent_modeling_ forest_fire. 2008

2. Beitman G, Erdeii A. Vysshie transtsendentnye funktsii. Gipergeometricheskaya funktsiya. Funktsii Lezhandra [Higher transcendental functions]. Moscow: Nauka, 1965. 296 p.

3. Leri M. M., Pavlov Yu. L. Lesnoi pozhar na sluchainom grafe so sgoraemymi rebrami [Forest fire on random graph with inflammable edges] Uchenye zapiski Petrozavodskogo gosudarstvennogo universiteta. 2013. N 2 (131). P. 96-99.

4. Fikhtengol'ts G. M. Kurs differentsial'nogo i integral'nogo ischisleniya. [Differential and integral calculus] T. 2. Sankt-Peterburg: Lan', 1997. 800 p.

5. Durrett R. Random graph dynamics. Cambridge University Press. 2006. doi: 10.1017/CB09780511546594

6. Faloutsos C., Faloutsos P., Faloutsos M. On power-law relationship of the Internet topology. Computer communications Rev. 1999. Vol. 29. P. 251-262. doi: 10.1145/316194.316229

7. Flajolet P., Sedgewick R. Analytic combinatorics. Cambridge University Press. 2009. doi: 10.1017/CB09780511801655

8. Hofstad R. Random graphs and complex networks. Eindhoven university of technology. 2011. 363 p.

9. Laurinskas A., Garunksis R. The Lerch zeta-function. Dordrecht: Kluwer, 2002. 189 p.

10. Norros I., Reittu H. 0n the power-law random graph model of massive data networks. Performance Evaluation. 2004. Vol. 55, N 4. P. 3-23.

11. Pavlov Yu. L., Feklistova E. V. Limit distributions of the edge number in random configuration graph. European researcher. 2013. Vol. 48, N 5-1. P. 1097-1100.

Received April 03, 2015

СВЕДЕНИЯ ОБ АВТОРАХ:

CONTRIBUTORS:

Павлов Юрий Леонидович

зав. лаб. теории вероятностей и компьютерной статистики, д. ф.-м. н., профессор Институт прикладных математических исследований Карельского научного центра РАН ул. Пушкинская, 11, Петрозаводск, Республика Карелия, Россия, 185910 эл. почта: pavlov@krc.karelia.ru тел.: (8142) 781218

Феклистова Елена Валерьевна

аспирант лаб. теории вероятностей и компьютерной статистики

Институт прикладных математических исследований Карельского научного центра РАН ул. Пушкинская, 11, Петрозаводск, Республика Карелия, Россия, 185910 эл. почта: f_len@mail.ru тел.: (8142) 781218

Pavlov, Yury

Institute of Applied Mathematical Research,

Karelian Research Centre,

Russian Academy of Sciences

11 Pushkinskaya St., 185910 Petrozavodsk,

Karelia, Russia

e-mail: pavlov@krc.karelia.ru

tel.: (8142) 781218

Feklistova, Elena

Institute of Applied Mathematical Research,

Karelian Research Centre,

Russian Academy of Sciences

11 Pushkinskaya St., 185910 Petrozavodsk,

Karelia, Russia

e-mail: f_len@mail.ru

tel.: (8142) 781218