| 1. |
- Abola, Benard
(författare)
-
Perturbed Markov Chains with Damping Component and Information Networks
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis brings together three thematic topics, PageRank of evolving tree graphs, stopping criteria for ranks and perturbed Markov chains with damping component. The commonality in these topics is their focus on ranking problems in information networks. In the fields of science and engineering, information networks are interesting from both practical and theoretical perspectives. The fascinating property of networks is their applicability in analysing broad spectrum of problems and well established mathematical objects. One of the most common algorithms in networks' analysis is PageRank. It was developed for web pages’ ranking and now serves as a tool for identifying important vertices as well as studying characteristics of real-world systems in several areas of applications. Despite numerous successes of the algorithm in real life, the analysis of information networks is still challenging. Specifically, when the system experiences changes in vertices /edges or it is not strongly connected or when a damping stochastic matrix and a damping factor are added to an information matrix. For these reasons, extending existing or developing methods to understand such complex networks is necessary.Chapter 2 of this thesis focuses on information networks with no bidirectional interaction. They are commonly encountered in ecological systems, number theory and security systems. We consider certain specific changes in a network and describe how the corresponding information matrix can be updated as well as PageRank scores. Specifically, we consider the graph partitioned into levels of vertices and describe how PageRank is updated as the network evolves.In Chapter 3, we review different stopping criteria used in solving a linear system of equations and investigate each stopping criterion against some classical iterative methods. Also, we explore whether clustering algorithms may be used as stopping criteria.Chapter 4 focuses on perturbed Markov chains commonly used for the description of information networks. In such models, the transition matrix of an information Markov chain is usually regularised and approximated by a stochastic (Google type) matrix. Stationary distribution of the stochastic matrix is equivalent to PageRank, which is very important for ranking of vertices in information networks. Determining stationary probabilities and related characteristics of singularly perturbed Markov chains is complicated; leave alone the choice of regularisation parameter. We use the procedure of artificial regeneration for the perturbed Markov chain with the matrix of transition probabilities and coupling methods. We obtain ergodic theorems, in the form of asymptotic relations. We also derive explicit upper bounds for the rate of convergence in ergodic relations. Finally, we illustrate these results with numerical examples.
|
|
| 2. |
- Muhumuza, Asaph Keikara, 1975-
(författare)
-
Extreme points of the Vandermonde determinant in numerical approximation, random matrix theory and financial mathematics
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis discusses the extreme points of the Vandermonde determinant on various surfaces, their applications in numerical approximation, random matrix theory and financial mathematics. Some mathematical models that employ these extreme points such as curve fitting, data smoothing, experimental design, electrostatics, risk control in finance and method for finding the extreme points on certain surfaces are demonstrated.The first chapter introduces the theoretical background necessary for later chapters. We review the historical background of the Vandermonde matrix and its determinant, some of its properties that make it more applicable to symmetric polynomials, classical orthogonal polynomials and random matrices.The second chapter discusses the construction of the generalized Vandermonde interpolation polynomial based on divided differences. We explore further, the concept of weighted Fekete points and their connection to zeros of the classical orthogonal polynomials as stable interpolation points.The third chapter discusses some extended results on optimizing the Vandermonde determinant on a few different surfaces defined by univariate polynomials. The coordinates of the extreme points are shown to be given as roots of univariate polynomials.The fourth chapter describes the symmetric group properties of the extreme points of Vandermonde and Schur polynomials as well as application of these extreme points in curve fitting.The fifth chapter discusses the extreme points of Vandermonde determinant to number of mathematical models in random matrix theory where the joint eigenvalue probability density distribution of a Wishart matrix when optimized over surfaces implicitly defined by univariate polynomials.The sixth chapter examines some properties of the extreme points of the joint eigenvalue probability density distribution of the Wishart matrix and application of such in computation of the condition numbers of the Vandermonde and Wishart matrices. The seventh chapter establishes a connection between the extreme points of Vandermonde determinants and minimizing risk measures in financial mathematics. We illustrate this with an application to optimal portfolio selection.The eighth chapter discusses the extension of the Wishart probability distributions in higher dimension based on the symmetric cones in Jordan algebras. The symmetric cones form a basis for the construction of the degenerate and non-degenerate Wishart distributions.The ninth chapter demonstrates the connection between the extreme points of the Vandermonde determinant and Wishart joint eigenvalue probability distributions in higher dimension based on the boundary points of the symmetric cones in Jordan algebras that occur in both the discrete and continuous part of the Gindikin set.
|
|
| 3. |
- Seleka Biganda, Pitos, 1981-
(författare)
-
Analytical and Iterative Methods of Computing PageRank of Networks
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis is about variants of PageRank, methods of PageRank computation and perturbation analysis of a PageRank vector as a stationary distribution of a kind of perturbed Markov chain model. Chapter 2 of this thesis gives closed form formulae for ordinary and lazy PageRanks for some specific simple line graphs. Different cases of changes made to the simple line graph are considered and for each case, a corresponding formula for each of the two variants of PageRank is provided.Chapter 3 is dedicated to the exploration of relationships that exist between three known variants of PageRank: ordinary PageRank, lazy PageRank and random walk with backstep PageRank in terms of their convergence and consistency in rank scores for different graph structures with reference to PageRank parameters, the damping factor c and backstep parameter β. In Chapter 4, we discuss numerical methods used in solving the PageRank problem as a linear system and evaluate some stopping criteria that can be employed in such methods. Finally, in Chapter 5, we address the PageRank problem as a first order perturbed Markov chain problem and study the perturbation analysis for stationary distributions of Markov chains with damping component. We illustrate our results on asymptotic perturbation analysis by using different computational examples.
|
|
| 4. |
|
|
