Random Models for Graphical Networks and their Degree Distributions

Abstract

Random models for complex network analysis is a very important topic and serves many areas of science such as biology, computing, social science, and transport, where their data can have a form of graphical representation. This thesis investigates the mechanism and properties of some existing random graph models such as the Erdős-Rényi model and the Watts-Strogatz model. The study employs analytical and numerical tools to analyse these models, with a focus on their degree distribution and parameter estimation. The analysis considers undirected, unweighted, and simple graphs. Both versions of the Erdős-Rényi model: G(n,p) and G(n,m) are studied, and some of their properties are computed and compared analytically. For the G(n,p) model, computational analysis is performed to demonstrate that its joint node degree distribution can be approximated by a multivariate normal distribution under certain conditions. Maximum likelihood estimation of the probability parameter (p) is then calculated, considering both independent and dependent degrees. A comparison of these estimators is conducted for varying values of the number of nodes (n). For the Watts-Strogatz model, discrepancies between the model's original description and its implementation in the igraph package in R are identified. A comparison between the two versions is made, and an approximate degree distribution is derived for the model based on the igraph implementation. Additionally, a heuristic argument is employed to compute an approximate variance of degrees for both versions, which is then utilized to provide an estimator for the rewiring probability. Due to the analytical challenges in the model of Watts-Strogatz, a new small world model is proposed as an alternative. This new model, referred to as G_k(n,{p,q}) when the number of edges is probabilistic and G_k(n,{m,w}) when it is deterministic, offers more simplicity in analysis and resolves the limited options for the number of edges in the Watts-Strogatz model. Exact degree distributions and expected clustering coefficients are derived for this new model. Finally, a novel dynamic model is developed, allowing for the adjustment of graph properties by varying the weight adjustment parameter (α). For positive values of α, the model exhibits both small world and preferential attachment properties simultaneously. In contrast, negative values of α lead to a level of regularity in degrees, which is advantageous for networks that demonstrate such regular patterns.