Один случай предельного поведения степеней вершин в условных конфигурационных графах

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

Аннотация


Рассматриваются конфигурационные графы с N
вершинами. Степени вершин являются независимыми одинаково
распределенными случайными величинами, имеющими дискретное
степенное распределение с параметром tau. Они равны числу
занумерованных в произвольном порядке полуребер. Граф строится
путем попарного равновероятного соединения полуребер для
образования ребер. Такие модели используются для описания
различных сетей коммуникаций и топологии сети Интернет. Мы
изучаем подмножество случайных графов при условии, что сумма
степеней известна и равна n. Свойства графа зависят от
поведения параметра tau. Пусть \tau является случайной
величиной, равномерно распределенной на отрезке
[a,b],0<a<b<ooПусть eta_{(N)} и mu_r равны
максимальной степени вершины и числу вершин заданной степени r.
Предельные распределения этих случайных величин при
N,n --> oo  так, что n/N --> oo ранее
были известны только если a < 1. В статье доказаны
предельные теоремы для eta_{(N)} и mu_r в случае a>1.

Ключевые слова


случайный конфигурационный граф; степень вершины; предельные теоремы.

Полный текст:

PDF

Литература


Ибрагимов И. А., Линник Ю. В. Независимые и стационарно связанные

величины. М.: Наука, 1965. 524~с.

Колчин В. Ф. Случайные графы. М.: Физматлит, 2000. 256~с.

Павлов Ю. Л. Один случай предельного распределения максимального

объема дерева в случайном лесе //~Математические заметки. 1979. Т. 25, вып. 5. С. 751--760.

Павлов Ю. Л. Об условных интернет-графах, степени вершин

которых не имеют математического ожидания //~Дискретная

математика. 2010. Т. 22, вып. 3. С. 20--33. doi: 10.4213/dm1104

Павлов Ю. Л. Об условных конфигурационных графах со случайным

распределением степеней вершин //~Труды КарНЦ РАН. 2016. № 8. С. 62--72. doi: 10.17076/mat313

Павлов Ю. Л., Дертишникова Е. Н. О предельном

распределении максимальной степени вершины в случайном графе

интернет-типа //~Труды КарНЦ РАН. 2010. № 3. С. 59--65.

Павлов Ю. Л., Чеплюкова И. А. Случайные графы

интернет-типа и обобщенная схема размещения //~Дискретная

математика. 2008. Т. 20, вып. 3. С. 3--18. doi: 10.4213/dm1008

Reittu H., Norros I. On the power-law random graph model

of massive data networks //~Performance Evaluation. 2004. Vol.

, no.~4. P. 3--23. doi: 10.1016/S0166-53/6(3)00097-x

References

Ibragimov I. A., Linnik Yu. V. Independent

and stationary sequences of random variables.

Groningen: Wolters Neordhoff Publ., 1971. 438 p.

Kolchin V. F. Random graphs. Cambridge:

Univ. Press, 1999. 252 p.

Pavlov Yu. L. A case of limit distribution of

the maximal volume on a tree in a random forest.

Mathematical Notes. 1979. Vol. 25, iss. 5. P. 387–

doi: 10.1515/dma.2007.034

Pavlov Yu. L. On conditional Internet graphs

whose vertex degrees have no mathematical

expectation. Discrete Mathematics and Applications.

Vol. 20, iss. 5–6. P. 509–524. doi:

1515/dma.2010.031

Pavlov Yu. L. Ob uslovnykh konfiguratsionnykh

graphakh so sluchainym raspredeleniem stepenei

vershin [On conditional configuration graphs with

random distribution of vertex degrees]. Trudy

KarNTs RAN [Trans. KarRC RAS]. 2016. No. 8.

P. 62–72.

Pavlov Yu. L., Dertishnikova E. N. O

predel’nom raspredelenii maksimal’noi stepeni

vershiny v sluchainom grafe internet-tipa [On the

limited distribution of the maximum vertex degree

in a random internet-type graph]. Trudy KarNTs

RAN [Trans. KarRC RAS]. 2010. No. 3, iss. 1.

P. 59–65. doi: 10.17076/mat313

Pavlov Yu. L., Cheplyukova I. A. Random

Internet-type graphs and the generalized

allocation scheme. Discrete Mathematics and

Applications. 2008. Vol. 18, iss. 5. P. 447–464. doi:

1515/DMA.2008.033

Reittu H., Norros I. On the powerlaw

random graph model of massive data

networks. Performance Evaluation. 2004. Vol. 55,

no. 4. P. 3–23. doi: 10.1016/S0166-53/6(3)00097-x




DOI: http://dx.doi.org/10.17076/mat613

Ссылки

  • На текущий момент ссылки отсутствуют.


© Труды КарНЦ РАН, 2014-2016