A general model of web graphs

Spurred on by the development of the World Wide Web, there has been considerable interest recently in developing models of graphs which reflect its (undirected) structure and that of other large complex networks. See for example \textit{B. Bollobas} and \textit{O. Riordan} [Mathematical results on scale-free random graphs. In: Handbook of graphs and networks: From the genome to the internet (Wiley, 2002)] for an overview. There are a number of experimental studies which suggest that such graphs often have an inverse power law for the proportion of vertices of given degree: that is, if the graph has \(n\) vertices, the number of vertices of the (fixed) degree \(k\) is asymptotically \(nCk^{-x}\) where \(x\) is a constant and \(C=1/(\sum_{k\in \mathbf N}k^{-x})\). This is in contrast to the situation in the usual Erdős-Rényi random graph \(G(n,p)\), where the number of vertices of degree \(k\) has a Poisson distribution (so is exponentially small in \(k\) for large \(k\)). The paper studies modelling such structures; that is, it investigates graph processes which evolve randomly and whose expected degree sequence obeys a power law as above. The basic framework is as follows. At time \(t=0\), there is a single vertex \(v_{0}\). At any time \(t\geq 1\), we already have a graph \(G(t-1)\). There are two cases. With probability \(1-\alpha\) a new node \(v\) is added to \(G(t-1)\). Then a random number of extra edges to be inserted, incident with \(v\), is chosen: this number is \(i\) with probability \(p_{i}\). Then with probability \(\beta\) the \(i\) other ends are chosen uniformly and at random from the vertices of \(G(t-1)\) other than \(v\); with probability \(1-\beta\) they are chosen with probability proportional to their degree. (This latter alternative is called `copying'and is typical of the web, where many newly created sites include links to other already popular sites, e.g. the national rail timetable). The second case (with, of course, probability \(\alpha\)) is that an existing vertex of \(G(t-1)\) is chosen: with probability \(\delta\) it is selected uniformly and at random from \(V(G(t-1))\), and with probability \(1-\delta\) it is chosen with probability proportional to its degree. Then \(i\) terminal vertices for the \(i\) new edges out of \(v\) are chosen; with probability \(\gamma\) they are chosen uniformly and at random, and with probability \(1-\gamma\) they are chosen by copying. To ensure a sensible form of evolution occurs, we require \(\alpha<1\) and \(p_{0}=q_{0}=0\): we also insist that the distributions \((p_{j})\) and \((q_{j})\) have finite support to simplify the difference equations studied in the analysis. The main results of the paper concern degree sequences. Rather than drowning in alphabet soup by attempting to state them precisely, we convey their flavour. Let \(D_{k}(t)\) be the number of vertices of degree \(k\) at time \(t\). The basic idea is that the random variable \(D_{k}(t)\) is concentrated around its expected value \(\bar{D}_{k}(t)\), and that \(\bar{D}_{k}(t)\) is well approximated by \(td_{k}\) where \(d_{k}\) is the solution of a certain difference equation depending on the parameters. More precisely, it is shown that there is a constant \(M>0\) such that almost surely, for all \(t,k\geq 1\), \(|\bar{D}_{k}(t)-td_{k}|\leq Mt^{1/2}\log(t)\). It is then shown that (provided some mild conditions, called the `solution conditions\', hold) \(d_{k}=C(1+O(1/k))k^{-x}\) for a certain \(x\) determined by \(\alpha,\beta,\gamma,\delta\) and the distributions \((p_{i})\) and \((q_{i})\), provided some copying occurs. The precise concentration statement is that, for \(1\leq k\leq t^{1/21}\) and for some sufficiently large \(M\), \[ P\{|D_{k}(t)-\bar{D}_{k}(t)|\geq Mt^{3/4}\}\leq t^{-\Omega(\log(t))}. \] In the case when the process is restricted (that is, the decisions as to whether or not to add a new node, and how many edges to add at each stage are non-random) an alternative concentration bound is given. Finally, the order of magnitude of the maximum degree of the graph at time \(t\) is determined (under technical conditions). The main technical point is the solution of a certain difference equation with non-constant coefficients. In certain special cases a solution can be found easily, but in general the solution depends on facts about Laplace's method for linear difference equations with rational coefficients; see e.g. \textit{I. M. Milne-Thomson} [``The calculus of finite differences (1933; Zbl 0008.01801)]. The concentration results depend, unsurprisingly, on the Azuma-Hoeffding martingale inequality, but a fair amount of detailed analysis of the process is also required. Finally the authors remark that one can instead consider directed variants, since the description in the second paragraph of how edges arise is easily seen to imply a natural orientation on the edges. Again power-law asymptotic formulae for a suitable analogue of \(d_{k}\) are obtained, using similar techniques to the undirected case.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: A general model of web graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4805220)