zbMATH — the first resource for mathematics

Random graphs of internet type and the generalised allocation scheme. (English. Russian original) Zbl 1171.05419
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.

05C80 Random graphs (graph-theoretic aspects)
90B80 Discrete location and assignment
Full Text: DOI
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.