It's a small world for random surfers (Q329281)

This paper gives logarithmic upper bounds for the diameters of the random-surfer webgraph model and the PageRank-based selection webgraph model. The random-surfer webgraph model on \(n\) vertices is defined as follows. Let \(d\) be a positive integer and \(0<p\leq1\). Start with a single vertex \(v_0\) with \(d\) self-loops. At each step \(1\leq s\leq n-1\), a new vertex \(v_s\) appears and \(d\) edges are created from it to existing vertices by conducting the following procedure \(d\) times: choose a vertex \(u\) uniformly from the existing vertices and a new geometric random variable \(X\) with parameter \(p\); perform a simple random walk of length \(X\) starting from \(u\) and connect \(v_s\) to the last vertex of the walk. It is shown that a.a.s. the diameter of this model is at most \(8e^p(\ln n)/p\) in the limit of \(n\). In the case of \(d=1\), close upper and lower bounds for the diameters of both models are given.