| 1. |
- Abola, Benard, et al.
(författare)
-
Chapter 2. Nonlinearly Perturbed Markov Chains and Information Networks
- 2021
-
Ingår i: Applied Modeling Techniques and Data Analysis 1. - Hoboken, NJ : John Wiley & Sons. - 9781786306739 - 9781119821564 ; , s. 23-55
-
Bokkapitel (refereegranskat)abstract
- This chapter is devoted to studies of perturbed Markov chains, commonly used for the description of information networks. In such models, the matrix of transition probabilities for the corresponding Markov chain is usually regularized by adding aspecial damping matrix, multiplied by a small damping (perturbation) parameter ε. In this chapter, we present the results of detailed perturbation analysis of Markov chains with damping component and numerical experiments supporting and illustrating the results of this perturbation analysis.
|
|
| 2. |
- Abola, Benard, et al.
(författare)
-
Nonlinearly Perturbed Markov Chains and Information Networks
- 2019
-
Ingår i: Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019. - : ISAST: International Society for the Advancement of Science and Technology. - 9786185180331 ; , s. 51-79
-
Konferensbidrag (refereegranskat)abstract
- The paper is devoted to studies of perturbed Markov chains commonly used for description of information networks. In such models, the matrix of transition probabilities for the corresponding Markov chain is usually regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. In this paper, we present results of the detailed perturbation analysis of Markov chains with damping component and numerical experiments supporting and illustrating the results of this perturbation analysis.
|
|
| 3. |
|
|
| 4. |
- 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.
|
|
| 5. |
- 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.
|
|
| 6. |
- Silvestrov, Dmitrii, 1947-, et al.
(författare)
-
Asymptotic expansions for stationary and quasi-stationary distributions of perturbed semi-Markov processes
- 2016
-
Ingår i: ICNPAA 2016 World Congress. - New York : American Institute of Physics (AIP). - 0094-243X. - 9780735414648 ; , s. 1-9
-
Konferensbidrag (refereegranskat)abstract
- New algorithms for computing asymptotic expansions, without and with explicit upper bounds for remainders, for stationary and quasi-stationary distributions of nonlinearly perturbed semi-Markov processes are presented. The algorithms are based on special techniques of sequential phase space reduction, which can be applied to models with an arbitrary asymptotic communicative structure of phase spaces.
|
|
| 7. |
- Silvestrov, Dmitrii, 1947-, et al.
(författare)
-
Asymptotic Expansions for Stationary Distributions of Nonlinearly Perturbed Semi-Markov Processes. 1
- 2019
-
Ingår i: Methodology and Computing in Applied Probability. - : Springer Science and Business Media LLC. - 1387-5841 .- 1573-7713. ; 21:3, s. 945-964
-
Tidskriftsartikel (refereegranskat)abstract
- New algorithms for construction of asymptotic expansions for stationary distributions of nonlinearly perturbed semi-Markov processes with finite phase spaces are presented. These algorithms are based on a special technique of sequential phase space reduction, which can be applied to processes with an arbitrary asymptotic communicative structure of phase spaces. Asymptotic expansions are given in two forms, without and with explicit upper bounds for remainders.
|
|
| 8. |
- Silvestrov, Dmitrii, 1947-, et al.
(författare)
-
Asymptotic Expansions for Stationary Distributions of Nonlinearly Perturbed Semi-Markov Processes. 2
- 2019
-
Ingår i: Methodology and Computing in Applied Probability. - : Springer Science and Business Media LLC. - 1387-5841 .- 1573-7713. ; 21:3, s. 965-984
-
Tidskriftsartikel (refereegranskat)abstract
- Asymptotic expansions with explicit upper bounds for remainders are given for stationary distributions of nonlinearly perturbed semi-Markov processes with finite phase spaces. The corresponding algorithms are based on a special technique of sequen- tial phase space reduction, which can be applied to processes with an arbitrary asymptotic communicative structure of phase spaces.
|
|
| 9. |
|
|
| 10. |
|
|
