Communities and competition in random networks

Chellig, Jordan Liess Alexander (2023). Communities and competition in random networks. University of Birmingham. Ph.D.

Preview

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

Abstract

We consider two problems inspired by the social properties of large-scale random networks. Firstly, we consider evolutionary games on a population whose underlying topology of interactions is determined by a binomial random graph. Our focus is on 2-player symmetric games with 2 strategies played between the incident members of such a population. Players update their strategies synchronously. At each round, each player
selects the strategy that is the best response to the current set of strategies its neighbours play. We show rapid convergence to unanimity for p in a range that depends on a certain characteristic of the payoff matrix. In the case where the matrix possesses a further strategic bias, we determine a sharp threshold on p, above which the largest connected component reaches unanimity with high probability. For p below this critical value, where this does not happen, we identify those substructures inside the largest component that remain discordant throughout the evolution of the system. We consider extensions of this system into three or more strategies and declare unanimity for two specific cases
depending on entries in the payoff matrix.

Our final project considers graph modularity: a quantity that has been introduced in order to quantify how close a network is to an ideal modular network. In such an ideal network the nodes form small interconnected communities that are joined together with relatively few edges. In this thesis, we consider this quantity on a recent probabilistic model of complex networks introduced by Krioukov et al. This model views a complex network as an expression of hidden hierarchies, encapsulated by an underlying hyperbolic space. For certain parameters, this model was proved to have typical features that are observed in complex networks such as power-law degree distribution, bounded average degree, clustering coefficient that is asymptotically bounded away from zero, and ultra-small typical distances. We investigate its modularity and we show that, in this regime, it converges to 1 in probability.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):