Models of Random Web Graphs

Models of random graphs have been intensively studied during the last 50 years. For example, P. Erdős and A. Rényi proposed around 1960 two now classical models. In the first model, we fix two natural numbers $ n, M $ satisfying the condition $ 0 < M \le C_n^2 $. We also fix the set of vertices $ V_n = \{1, \dots, n\} $ and choose a random set of edges $ E $ of cardinality $ M $ according to the uniform distribution, i.e., the probability of $ E $ equals $ \frac{1}{C_{C_n^2}^M} $. In the second model, edges are chosen independently, each with probability $ p \in [0,1] $, so that we get a set of edges $ E $ with probability $ p^{|E|}(1-p)^{C_n^2-|E|} $.
Unfortunately, both of the Erdős–Rényi models cannot be applied to appropriately describe the growth of many “real world” networks such as social nertworks, biological networks, or Internet. In the last 15 years, several important new models appeared which use different random graph processes to incorporate various statistics of the World Wide Web.
In our talk, we shall give a survey of models of the so called random web graphs. We shall also present some “classical” and very recent probabilistic results concerning some of these models.