Evolving Inhomogeneous Random Structures

Iyer, Tejas (2021). Evolving Inhomogeneous Random Structures. University of Birmingham. Ph.D.

Preview

Iyer2022PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (3MB) | Preview

Abstract

We introduce general models of evolving, inhomogeneous random structures, where in each of the models either one or several nodes arrive at a time, and are equipped with random, independent weights. In the two evolving tree models we study, an existing vertex is chosen at each time-step with probability proportional to its fitness function, which is a function of its weight, and possibly the weights of its neighbours, and the newly arriving node(s) connect to it. The third models, with parameter $d$ consist of evolving sequences of $(d-1)$-dimensional simplicial complexes. At each time-step a $(d-1)$-simplex is sampled with probability proportional to a function of the weights of the vertices the $(d-1)$-simplex contains. In both variants, Model~\textbf{A} and Model~\textbf{B}, for each subset $S$ of size $(d-2)$, we add the simplex consisting of $S$ and the single new-coming vertex. Additionally, in Model~\textbf{B}, the selected simplex is removed from the simplicial complex.

In each of the models we study the limiting proportion of vertices in the structure with a given degree, showing that, in general, this limit exists in probability, and behaves like a type of \emph{generalised geometric distribution}. In the evolving tree models, we actually study a more general quantity: the empirical measures associated with the number of vertices with a given degree and weight. With regards to this quantity, when normalised by the size of the network, we also show that the limit exists and belongs to a certain universal class. Depending on various assumptions, we prove that for any measurable set, the measure of that set converges either almost surely or in probability to its measure under this deterministic limit.

In the evolving tree models, we also study another quantity: the empirical measure corresponding to the proportion of edges in the structure with endpoint having a given weight. We show that, when normalised by the number of edges in the tree, under certain assumptions, this quantity also converges to a deterministic limiting measure, in the sense that for any measurable set, the measure of that set converges either almost surely. However, when the trees take certain forms, which we call the GPAF-tree, or the PANI-tree, we show that interesting, non-trivial behaviour can emerge when these assumptions fail. In particular, with regards to the GPAF-tree, we show that this model can exhibit condensation where a positive proportion of edges accumulate around vertices with weight that maximises the reinforcement of their fitness, or, more drastically, have a degenerate limiting degree distribution where the entire proportion of edges accumulate around these vertices. We also show that the condensation phenomenon extends to the more general PANI-tree model. As we will show, the latter two models have limiting distribution of degrees that behaves like an `averaged' power law, which may be of interest when considering them as toy models for the evolution of complex networks.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):