Giant components for two expanding graph processes
Motivated by an interest in finding a random model of the Internet, the authors discuss the following two random graph models. From the text: ``We are interested in the following random process UGROW with parameter a constant \(p\), with \(0< p\leq 1\), for constructing an undirected graph. 0. Initialize with the single vertex 1. 1. For \(i= 2,\dots, n\) add vertex \(i\) and with probability \(p\) add an edge between \(i\) and a vertex chosen uniformly at random from \(1,\dots, i-1\). We are interested in the following process DGROW for constructing a directed graph. Again the parameters \(0\leq p_{\text{down}}, p_{\text{extra}}\leq 1\) are constants, and all choices are independent. 0. Initialize with the single vertex \(1\). 1. For \(i= 2,\dots, n\) add vertex \(i\) and with probability \(p_{\text{down}}\) add an arc from \(i\) to a vertex chosen uniformly at random from \(1,\dots, i-1\). 2. For each ordered pair \((i,j)\) of vertices, add an arc from \(i\) to \(j\) with probability \(p_{\text{extra}}/(n-1)\). The authors study the emergence of giant components in these two models. For the entire collection see [Zbl 0997.00016].
This page was built for publication: Giant components for two expanding graph processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4428907)
