https://www.mdu.se/

Perturbed Markov chains are popular models for description of information networks. In such models, the transition matrix P₀ of an information Markov chain is usually approximated by matrix P^_ε = (1 - ε) P₀ + ε D, where D is a so-called damping stochastic matrix with identical rows and all positive elements, while ε is a damping (perturbation) parameter. We perform a detailed perturbation analysis for stationary distributions of such Markov chains, in particular get effective explicit series representations for the corresponding stationary distributions π_ε, upper bounds for the deviation |π_ε- π₀ |, and asymptotic expansions for πε with respect to the perturbation parameter ε.

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter epsilon. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems forn-step transition probabilities, as well as ergodic theorems in triangular array mode.

PageRank was initially defined by S. Brin and L. Page for the purpose of ranking homepages (nodes) based on the structure of links between these pages. Studies has shown that PageRank of a graph changes with changes in the structure of the graph. In this article, we examine how the PageRank changes when two or more outside nodes are connected to a line directed graph. We also look at the PageRank of a graph resulting from connecting a line graph to two complete graphs. In this paper we demonstrate that both the probability (or random walk on a graph) and blockwise matrix inversion approaches can be used to determine explicit formulas for the PageRanks of simple networks.

PageRank was initially defined by S. Brin and L. Page for the purpose of measuring the importance of web pages (nodes) based on the structure of links between them. Due to existence of diverse methods of random walk on the graph, variants of PageRank now exists. They include traditional (or normal) PageRank due to normal random walk and Lazy PageRank due to lazy random walk on a graph. In this article, we establish how the two variants of PageRank changes when complete graphs are connected to a line of nodes whose links between the nodes are in one direction. Explicit formulae for the two variants of PageRank are presented. We have noted that the ranks on a line graph are the same except their numerical values which differ. Further, we have observed that both normal random walk and lazy random walk on complete graphs spend almost the same time at each node.

PageRank is an algorithm for ranking web pages. It is the first and best known webgraph-based algorithm in the Google search engine. The algorithm is simple, robust and reliable to measure the importance of web pages. This chapter presents a comparative review of three variants of PageRank, namely ordinary PageRank (introduced by Brin and Page as a measure of importance of a web page), lazy PageRank and random walk with backstep PageRank. It compares the variants in terms of their convergence and consistency in rank scores for different graph structures with reference to PageRank’s parameters, damping factor and backstep parameter. The chapter also shows that ordinary PageRank can be formulated from the other two variants by some proportionality relationships.

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.

Bioinformatics, internet search engines (web pages) and social networks are some of the examples with large and high sparsity matrices. For some of these systems, only the actual ranks of the solution vector is interesting rather than the vector itself. In this case, it is desirable that the stopping criterion reflects the error in ranks rather than the residual vector that might have a lower convergence. This chapter evaluates stopping criteria on Jacobi, successive over relaxation (SOR) and power series iterative schemes. Numerical experiments were performed and results show that Kendall's correlation coefficient gives good stopping criterion of ranks for linear system of equations. The chapter focuses on the termination criterion as means of obtaining good ranks. It outlines some studies carried out on stopping criteria in solving the linear system.