Abstract
This thesis is concerned with two classes of evolving random graph models in random environment: preferential attachment models with additive fitness, as originally defined by Ergun and Rodgers, and weighted recursive graphs, as defined by Hiesmayr and Islak. These models are generalisations of affine preferential attachment models and random recursive trees, respectively, and the random environment represents the inhomogeneity naturally present in real-world networks. In this thesis we study the properties of these models to understand the effect of the random environment on the evolution of the graph, and we indicate how and why the behaviour of the models in random environment differs from the classical models. In particular, we focus on the behaviour of the degree distribution and the maximum degree of these models.For the preferential attachment model with additive fitness we consider a heavy-tailed fitness distribution and observe a phase transition in the tail exponent of the fitness distribution with respect to the behaviour of the degree distribution and maximum degree. When the fitness distribution has a light tail, we observe behaviour similar to the classical models in the sense that one of the old vertices attains the maximum degree irrespective of fitness, whereas significantly different behaviour is observed for sufficiently heavy-tailed fitness distributions, in which case the maximum degree vertex has to satisfy the right balance between fitness and age.
For the weighted recursive graph model we consider a wide range of vertex-weight distributions for which different behaviour can be observed. For distributions with unbounded support we observe that the maximum degree vertex again has to satisfy the right balance between a high vertex-weight and age. For distributions with bounded support we observe behaviour similar to the random recursive tree, at least to first order. Higher-order corrections of the maximum degree are highly dependent on the underlying vertex-weight distribution and here the behaviour can again differ significantly from what is observed for the random recursive tree.
| Date of Award | 8 Sept 2021 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Marcel Ortgiese (Supervisor) & Alexandre De Oliveira Stauffer (Supervisor) |