Random graphs of internet type and the generalised allocation scheme. (English. Russian original) Zbl 1171.05419

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

Discrete Math. Appl. 18, No. 5, 447-463 (2008); translation from Diskretn. Mat. 20, No. 3, 3-18 (2008).

Summary: 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 \geq 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.

MSC:

05C80	Random graphs (graph-theoretic aspects)
90B80	Discrete location and assignment

References:

[1]	Faloutsos C., Computer Communications Rev. 29 pp 251– (1999) · doi:10.1145/316194.316229
[2]	Reittu H., Performance Evaluation 55 pp 3– (2004) · doi:10.1016/S0166-5316(03)00097-X
[3]	Newman M. E. J., Phys. Rev. E 64 pp 026118– (2001) · doi:10.1103/PhysRevE.64.026118
[4]	Yu., Discrete Math. Appl. 17 pp 425– (2007) · Zbl 1247.05220 · doi:10.1515/dma.2007.034
[5]	Mukhin A. B., Theory Probab. Appl. 36 pp 698– (1991) · Zbl 0776.60027 · doi:10.1137/1136086
[6]	Kolchin A. V., Discrete Math. Appl. 13 pp 627– (2003) · Zbl 1046.60019 · doi:10.1515/156939203322733336
[7]	Kolchin A. V., Discrete Math. Appl. 16 pp 527– (2006) · Zbl 1129.60010 · doi:10.1515/156939206779218023