This article is cited in 19 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,\dots$, 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.

UDC: 519.2

Received: 10.07.2007

DOI: 10.4213/dm1008

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

Bibliographic databases:

• 
• 
• 
•