# zbMATH — the first resource for mathematics

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
Full Text:
##### References:
  Abello J., Algorithms–ESA1998 (Venice, 1998) pp 332– (1998)  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  Aiello W., Handbook of massive data sets 2  Albert R., Nature 401 (1999)  Alon N., The probabilistic method (1992)  Barabási A., Science 286 (1999)  DOI: 10.1016/S0378-4371(00)00018-2 · doi:10.1016/S0378-4371(00)00018-2  Erdös P., Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 pp 17– (1960)  DOI: 10.1007/BF02066689 · Zbl 0103.16302 · doi:10.1007/BF02066689  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  Hayes B., American Scientist 88 pp 104– (2000)  DOI: 10.1007/3-540-48686-0_1 · doi:10.1007/3-540-48686-0_1  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]  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  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]  Luczak T., Random graphs (Poznań, 1989) 2 pp 165– (1992)  DOI: 10.1002/rsa.3240060204 · Zbl 0823.05050 · doi:10.1002/rsa.3240060204  DOI: 10.1017/S0963548398003526 · Zbl 0916.05064 · doi:10.1017/S0963548398003526  DOI: 10.1016/S0095-8956(81)80021-4 · Zbl 0442.05043 · doi:10.1016/S0095-8956(81)80021-4  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. 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.