×

A random graph model for power law graphs. (English) Zbl 0971.05100

This paper introduces a random graph model of the world wide web. Fix \(\alpha\) and \(\beta\), and a distribution \(P(\alpha, \beta)\) assigns a uniform probability to a class of multigraphs such that, for any such multigraph, the number of vertices of a degree \(d\) is \(\lfloor e^{\alpha}/d^{\beta} \rfloor\). This model approximates the observed structure of the world wide web in some aspects. In studying the asymptotics of this model, \(\beta > 0\) is fixed, while \(\alpha\) is permitted to grow (and as \(\alpha\) increases, so does the expected order and size of the multidigraphs). The results in this paper concern the sizes of the connected components of random graphs in the spaces \(P(\alpha, \beta)\), for various \(\beta\), as \(\alpha \to \infty\).
(1) If \(\beta > 3.47875 \ldots\), then a.s.{} there is no giant component. They present estimates of the sizes of the small components. (2) If \(\beta < 3.47875 \ldots\), then a.s.{} the graph has a giant component. (3) If \(2 < \beta < 3.47875 \ldots\), the second largest component is a.s.{} log-sized; if \(\beta = 2\), the second largest component is a.s.{} log/loglog-sized; if \(2 > \beta > 1\), the second component is a.s.{} size \(\Theta(1)\). (4) If \(\beta < 1\), then the graph is a.s.{} connected.
The proofs rely on martingale arguments. While this model and its properties are interesting, expository problems occasionally make the meaning of passages in the proofs difficult to ascertain.
Reviewer: G.L.McColm (Tampa)

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C07 Vertex degrees

References:

[1] Abello J., Algorithms–ESA1998 (Venice, 1998) pp 332– (1998)
[2] Aiello, W., Chung, F. and Lu, L. ”A random graph model for massive graphs”. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000, Portland, OR. pp.171–180. New York: ACM Press. [Aiello et al. 2000] · Zbl 1296.05172
[3] Aiello W., Handbook of massive data sets 2
[4] Albert R., Nature 401 (1999)
[5] Alon N., The probabilistic method (1992)
[6] Barabási A., Science 286 (1999)
[7] DOI: 10.1016/S0378-4371(00)00018-2 · doi:10.1016/S0378-4371(00)00018-2
[8] Erdös P., Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 pp 17– (1960)
[9] DOI: 10.1007/BF02066689 · Zbl 0103.16302 · doi:10.1007/BF02066689
[10] Faloutsos, M., Faloutsos, P. and Faloutsos, C. ”On power-law relationships of the internet topology”. ACM SIGCOMM 1999 Conference: applications, technologies, architectures, and protocols for computer communications. 1999, Cambridge, MA. pp.251–262. New York: ACM Press. [Faloutsos et al. 1999] · Zbl 0889.68050
[11] Hayes B., American Scientist 88 pp 104– (2000)
[12] DOI: 10.1007/3-540-48686-0_1 · doi:10.1007/3-540-48686-0_1
[13] Kumar, S. R., Raghavan, P., Rajagopalan, S. and Tomkins, A. ”Trawling the web for emerging cyber communities”. Proceedings of the 8th World Wide Web Conference. 1999, Toronto. Amsterdam: Elsevier. [Kumar et al. 1999a]
[14] Kumar, S. R., Raghavan, P., Rajagopalan, S. and Tomkins, A. ”Extracting large-scale knowledge bases from the web”. VLDB1999, Proceedings of 25th International Conference on Very Large Data Bases. 1999, Edinburgh. Edited by: Atkinson, M. P. pp.639–650. San Francisco: Morgan Kaufmann. [Kumar et al. 1999b], Seehttp://www.informatik.uni-trier.de/-ley/db/conf/vldb/vldb99.html
[15] Kumar, S. R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. and Upfal, E. ”Stochastic models for the Web graph”. Proceedings of the 41st Annual Symposium on Foundations of Computer Science. 2000, Redondo Beach, CA. Los Alamitos, CA: IEEE. [Kumar et al. 2001]
[16] Luczak T., Random graphs (Poznań, 1989) 2 pp 165– (1992)
[17] DOI: 10.1002/rsa.3240060204 · Zbl 0823.05050 · doi:10.1002/rsa.3240060204
[18] DOI: 10.1017/S0963548398003526 · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[19] DOI: 10.1016/S0095-8956(81)80021-4 · Zbl 0442.05043 · doi:10.1016/S0095-8956(81)80021-4
[20] Wormald N. C., Surveys in combinatorics (Canterbury, 1999) pp 239– (1999) · doi:10.1017/CBO9780511721335.010
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.