Giant components for two expanding graph processes (Q4428907)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1984542
Language Label Description Also known as
default for all languages
No label defined
    English
    Giant components for two expanding graph processes
    scientific article; zbMATH DE number 1984542

      Statements

      22 September 2003
      0 references
      0 references
      0 references
      0 references
      Giant components for two expanding graph processes (English)
      0 references
      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].
      0 references

      Identifiers