The public defense of Benard Abola´s doctoral thesis in Mathematics/Applied Mathematics
The public defense of Bernard Abola´s doctoral thesis in Mathematics/Applied Mathematics will take place at 15.15 on December 10, 2020.
Title: ”Perturbed Markov Chains with Damping Component and Information Networks”
The faculty examiner is Professor Vladimir Anisimov, Center for Design and Analysis at Amgen Inc. The examining committee consists of v Associate Professor Olga Liivapuu, Estonian University of Life Sciences, Professor Christos Skiadas, Technical University of Crete and Professor Oleg Seleznjev, Umeå University.
Reserve: Professor Guglielmo D’Amico, University G. d’Annunzio of Chieti-Pescara and Associate Professor Oleksandr Borisenko, Taras Shevchenko National University of Kyiv.
The doctoral thesis has serial number 326.
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.
Register to take part
To be able to participate in the PhD defense, you need to pre-apply to administrative research support staff Marja Mutikainen firstname.lastname@example.org by informing your name and e-mail. You also need to inform if you wish to take part in Zoom or in the room. Last day to register is December 9, 2020.