General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Diskr. Mat., 2008, Volume 20, Issue 3, Pages 3–18 (Mi dm1008)  

This article is cited in 12 scientific papers (total in 12 papers)

Random graphs of Internet type and the generalised allocation scheme

Yu. L. Pavlov, I. A. Cheplyukova

Abstract: In order to simulate complex telecommunication networks, in particular, the Internet, random graphs are frequently used which contain $N$ vertices whose degrees are independent random variables distributed by the law
$$ \mathbf P\{\eta\ge k\}= k^{-\tau},$$
where $\eta$ is the vertex degree, $\tau>0$, $k=1,2,…$, and the graphs with identical degrees of all vertices are equiprobable. In this paper we consider the set of these graphs under the condition that the sum of degrees is equal to $n$. We show that the generalised scheme of allocating particles into cells can be used to investigate the asymptotic behaviour of these graphs. For $N,n\to\infty$ in such a way that $1<n/N<\zeta(\tau)$, where $\zeta(\tau)$ is the value of the Riemann zeta function at the point $\tau$, we obtain limit distributions of the maximum degree and the number of vertices of a given degree.


Full text: PDF file (171 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2008, 18:5, 447–463

Bibliographic databases:

UDC: 519.2
Received: 10.07.2007

Citation: Yu. L. Pavlov, I. A. Cheplyukova, “Random graphs of Internet type and the generalised allocation scheme”, Diskr. Mat., 20:3 (2008), 3–18; Discrete Math. Appl., 18:5 (2008), 447–463

Citation in format AMSBIB
\by Yu.~L.~Pavlov, I.~A.~Cheplyukova
\paper Random graphs of Internet type and the generalised allocation scheme
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 3
\pages 3--18
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 5
\pages 447--463

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Yu. L. Pavlov, “On the limit distributions of the vertex degrees of conditional Internet graphs”, Discrete Math. Appl., 19:4 (2009), 349–359  mathnet  crossref  crossref  mathscinet  elib
    2. Yu. L. Pavlov, “On conditional Internet graphs whose vertex degrees have no mathematical expectation”, Discrete Math. Appl., 20:5-6 (2010), 509–524  mathnet  crossref  crossref  mathscinet  elib
    3. Pavlov Yu.L., Dertishnikova E.N., “O predelnom raspredelenii maksimalnoi stepeni vershiny v sluchainom grafe internet-tipa”, Tr. Karelskogo nauchnogo tsentra RAN, 2010, no. 3, 59–65  elib
    4. Pavlov Yu.L., Cheplyukova I.A., “Ob asimptotike statistiki tipa $\chi^2$ dlya internet-grafov”, Tr. Karelskogo nauchnogo tsentra RAN, 2010, no. 3, 66–71  elib
    5. Pavlov Yu.L., “O tipichnoi strukture konfiguratsionnogo internet-grafa s izvestnym chislom svyazei”, Trudy Karelskogo nauchnogo tsentra RAN, 2011, no. 5, 86–96  elib
    6. Cheplyukova I.A., “O predelnykh raspredeleniyakh nekotorykh chislovykh kharakteristik internet-grafov”, Trudy Karelskogo nauchnogo tsentra RAN, 2012, no. 5, 110–121  elib
    7. Pavlov Yu.L., “O predelnykh raspredeleniyakh stepenei vershin uslovnogo konfiguratsionnogo sluchainogo grafa”, Trudy Karelskogo nauchnogo tsentra RAN, 2012, no. 5, 78–88  elib
    8. Yu. L. Pavlov, E. V. Khvorostyanskaya, “On the limit distributions of the degrees of vertices in configuration graphs with a bounded number of edges”, Sb. Math., 207:3 (2016), 400–417  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    9. Yu. L. Pavlov, E. V. Feklistova, “On limit behavior of maximum vertex degree in a conditional configuration graph near critical points”, Discrete Math. Appl., 27:4 (2017), 213–222  mathnet  crossref  crossref  mathscinet  isi  elib
    10. Yu. L. Pavlov, “Conditional configuration graphs with discrete power-law distribution of vertex degrees”, Sb. Math., 209:2 (2018), 258–275  mathnet  crossref  crossref  adsnasa  isi  elib
    11. Yu. L. Pavlov, I. A. Cheplyukova, “On the asymptotics of degree structure of configuration graphs with bounded number of edges”, Discrete Math. Appl., 29:4 (2019), 219–232  mathnet  crossref  crossref  isi  elib
    12. Yu. L. Pavlov, “O svyaznosti konfiguratsionnykh grafov”, Diskret. matem., 31:2 (2019), 114–122  mathnet  crossref  elib
  • Дискретная математика
    Number of views:
    This page:649
    Full text:170
    First page:31

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020