Percolation and Random Walks on Preferential Attachment Models

Preferential attachment models are paradigmatic models for complex networks. In them, the high-variability of nodal degrees arises through the simple preferential dynamics of the addition of vertices and edges. In particular, vertices with high degrees are more likely to attract new edges than vertices with low degrees. In this project, we investigate processes living on such networks, focussing initially on percolation and later extending to random walks.

We use the notion of local weak convergence to identify the phase transition of percolation on preferential attachment models. This phase transition is expected to be rather different from percolation phase transitions on related random graph models, such as the configuration model and rank-1 inhomogeneous random graphs, in that it is so-called infinite order. That means that just above the critical value, the giant is extremely small. We then continue to study what happens closer to the critical value. Can we describe the critical window of this model, and what does it look like?

The local weak limit is tree-like, and this suggests that random walks on the graph mix in time proportional to the log of the size of the graph. Can we show this? Can we show that cut-off behavior occurs, and identify the constant at which the cut-off transition occurs?