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

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

Аннотация


Рассматриваются конфигурационные графы с N вершинами. Степени вершин являются независимыми одинаково распределенными случайными величина- ми, подчиняющимися степенному закону. Они определяют занумерованные в произвольном порядке полуребра. Граф образуется путем попарного равновероятного соединения полуребер для формирования ребер. Такие модели можно использовать для описания различных сетей коммуникаций и топологии сети Интернет. Мы изучаем подмножество случайных графов при условии, что сумма степеней вершин равна n. Свойства графа зависят от значения параметра τ распределения степеней вершин. Пусть µr означает число вершин степени r. Получены предельные распределения µr при N, n → ∞ и всех возможных значениях r и τ . Также в нашей модели параметр τ может изменяться вместе с N, n.

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


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

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

PDF

Литература


Бейтман Г., Эрдейи А. Высшие трансцендентные функции.

Гипергеометрическая функция. Функции Лежандра. М.: Наука, 1965.

с.

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

Павлов Ю. Л. Предельные распределения объема гигантской

компоненты в случайном графе Интернет-типа //~Дискретная

математика. 2007. Т. 19, вып. 3. С. ~22--34. doi: 10.4213/dm963

Павлов Ю. Л., Степанов М. М. Предельные распределения

числа петель случайного конфигурационного графа //~Труды МИАН им.~В.~А.~Стеклова. 2013. Т. 282. С. ~212--230. doi:

1134/S0371968513030175

Павлов Ю. Л., Феклистова Е. В. О предельном поведении

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

вблизи критических точек //~Дискретная математика. 2016. Т. 28,

вып. 2 (в печати).

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

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

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

Самосват Е. А. Моделирование Интернета с помощью

случайных графов: дис. ... канд. физ.-мат. наук. М., 2014. 98~с.

Aiello W., Chang F., Lu L. A random graph

model for massive graphs // Proceedings of the

nd ACM Symposium on theory of computing.

P. 171–180.

Bianconi G., Barabasi A.-L. Bose-Einstein

condensation in complex networks // Physical

Review Letters. 2001. Vol. 86. P. 5632–5635. doi:

1103/PhysRevLett.86.5632

Bollobas B. A probabilistic proof of an

asymptotic formula for the number of labelled

regular graphs // Eur. J. Comb. 1980. Vol. 1.

P. 311–316. doi: 10.1016/S0195-6698(80)80030-8

Durrett R. Random graph dynamics.

Cambridge University Press. 2006. doi:

1017/CBO9780511546594

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

Leri M., Pavlov Yu. Power-law random graphs

robustness: link saving and forest fire model

// Austrian Journal of Statistics. 2014. Vol. 43,

iss. 4. P. 229–236. doi: 10.17713/asj.v.43i4.34

Reittu H., Norros I. On the power-law

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

Wats D. J., Strogats S. H. Collective dynamics

of "small-word"networks // Nature, 1998. Vol. 393.

P. 440–442. doi: 10.1038/30916

References

Bateman H., Erdelyi A. Higher transcendental

functions. Vol. 1. New York; Toronto; London:

Megraw-hill book company, inc, 1953. 317 p.

Kolchin V. F. Random graphs. Cambridge:

University Press, 1999. 252 p.

Pavlov Yu. L. The limit distribution of the

size of a giant component in an Internettype

random graph. Discrete Mathematics and

Applications. 2007. Vol. 17, iss. 5. P. 425–438. doi:

1515/dma.2007.034

Pavlov Yu. L., Stepanov M. M. Limit

distributions of the number of loops in a random

configuration graph. Proceedings of the Steklov

Institute of Mathematics. 2013. Vol. 282, iss. 1.

P. 202–219. doi: 10.1134/S0081543813060175

Pavlov Yu. L., Feklistova E. V. On limit

behavior of the maximum vertex degrees in a

conditional configuration graph near critical points.

Discrete Mathematics and Applications. 2016 (in

print).

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

graphs of Internet type and the generalised

allocation scheme. Discrete Mathematics and

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

1515/DMA.2008.033

Samosvat E. A. Modelirovanie Interneta s

pomoshju sluchainyh grafov [Internet modeling

with help of random graphs]: DSc (Cand. of Phys.-

Math.) thesis. Moscow, 2014. 98 p.

Aiello W., Chang F., Lu L. A random graph

model for massive graphs. Proceedings of the 32nd

ACM Symposium on theory of computing. 2000.

P. 171–180.

Bianconi G., Barabasi A.-L. Bose-Einstein

condensation in complex networks. Physical

Review Letters. 2001. Vol. 86. P. 5632–5635. doi:

1103/PhysRevLett.86.5632

Bollobas B. A probabilistic proof of an

asymptotic formula for the number of labelled

regular graphs. Eur. J. Comb. 1980. Vol. 1. P. 311–

doi: 10.1016/S0195-6698(80)80030-8

Durrett R. Random graph dynamics.

Cambridge University Press. 2006. doi:

1017/CBO9780511546594

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

Leri M., Pavlov Yu. Power-law random graphs

robustness: link saving and forest fire model.

Austrian Journal of Statistics. 2014. Vol., 43, iss. 4.

P. 229–236. doi: 10.17713/asj.v.43i4.34

Reittu H., Norros I. On the power-law

random graph model of massive data networks.

Performance Evaluation. 2004. Vol. 55, no. 4. P. 3–

doi: 10.1016/S0166-53/6(3)00097-x

Wats D. J., Strogats S. H. Collective dynamics

of "small-word"networks. Nature, 1998. Vol. 393.

P. 440–442. doi: 10.1038/30916




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

Ссылки

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


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