On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph |
| |
Authors: | Hüseyin Acan Boris Pittel |
| |
Abstract: | A uniform attachment graph (with parameter k), denoted Gn,k in the paper, is a random graph on the vertex set n], where each vertex v makes k selections from v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of Gn,k to show that the conductance of Gn,k is of order . We also study the bootstrap percolation on Gn,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set. |
| |
Keywords: | bootstrap percolation conductance connectivity uniform attachment graph |
|
|