О коэффициенте кластеризации конфигурационных графов

Ирина Александровна Чеплюкова, Irina Cheplyukova

Аннотация


Рассматриваются конфигурационные графы с N вершинами. Степени вершин графа являются независимыми одинаково распределенными случайными величинами, распределение которых является степенным распределением с положительным параметром τ, где τ = τ (N) изменяется в диапазоне 0 < c1 τ c2 < ∞ и может принимать не только фиксированные значения. Получены теоремы, описывающие предельное поведение коэффициента кластеризации для таких графов с числом вершин N, стремящимся к бесконечности.

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


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

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

PDF (English)

Литература


Bateman H., Erdelyi A. Higher transcendental functions. New York Toronto-London: MC GRAWHILL Book Company INC; 1953.

Bianconi G., Barabasi A.-L. Bose-Einstein condensation in complex networks. Phys. RevLett. 2001;86:5632–5635. doi:10.1103/PhysRevLett.86.5632

Bollobas B. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb. 1980;1(4):311–316.

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

Durrett R. Random graph dynamics. Cambridge: Cambridge University Press; 2007. 223 p. doi: 10.1017/CBO9780511546594

Faloutsos C., Faloutsos P., Faloutsos M. Onpower-law relationships of the internet topology. Comput. Commun. Rev. 1999;29(1):251–262. doi: 10.1145/316194.316229

Gnedenko B. Sur la distribution limite du terme maximum d’une s´erie al´etorie. Ann. Math.1943;44(3):423–453. doi: 10.2307/1968974

Hofstad R. Random graphs and complex networks. Vol. 1. Cambridge: Cambridge University Press; 2017. 337 p. doi: 10.1017/9781316779422

Newman M. E. J. The structure and function of complex networks. SIAM Rev. 2003;45(2):167–256. doi: 10.1137/S003614450342480

Pavlov Yu. L. On the asymptotics of the clustering coefficient in a configuration graph with unknown distribution of vertex degrees. Informatics and Applications. 2019;13(3):9–13. (In Russ.). doi: 10.14357/19922264190302

Pavlov Yu. L., Cheplyukova I. A. On the asymptotics of degree structure of configuration graphs with bounded number of edges. Discrete Mathematics and Applications. 2019;29(4):219–232. doi: 10.1515/dma 2019-0020

Reittu H., Norros I. On the power-law random graph model of massive data networks. Perform. Eval. 2004;55(1-2):3–23. doi: 10.1016/S0166- 5316(03)00097-X




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

Ссылки

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


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

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