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.7923545241355896
0 references
0.7766360640525818
0 references
0.7742021083831787
0 references
0.7691203951835632
0 references
0.7681384086608887
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