| 1. |
- Abola, Benard, 1971-, et al.
(author)
-
Evaluation of Stopping Criteria for Ranks in Solving Linear Systems
- 2019. - Chapter 10
-
In: Data Analysis and Applications 1: Clustering and Regression, Modeling‐estimating, Forecasting and Data Mining, Volume 2. - Hoboken, NJ, USA : John Wiley & Sons. - 9781119597568 - 9781786303820 ; , s. 137-152
-
Book chapter (peer-reviewed)abstract
- 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.
|
|
| 2. |
- Abola, Benard, 1971-, et al.
(author)
-
PageRank in evolving tree graphs
- 2018
-
In: Stochastic Processes and Applications. - Cham : Springer. - 9783030028244 ; , s. 375-390
-
Book chapter (peer-reviewed)abstract
- In this article, we study how PageRank can be updated in an evolving tree graph. We are interested in finding how ranks of the graph can be updated simultaneously and effectively using previous ranks without resorting to iterative methods such as the Jacobi or Power method. We demonstrate and discuss how PageRank can be updated when a leaf is added to a tree, at least one leaf is added to a vertex with at least one outgoing edge, an edge added to vertices at the same level and forward edge is added in a tree graph. The results of this paper provide new insights and applications of standard partitioning of vertices of the graph into levels using breadth-first search algorithm. Then, one determines PageRanks as the expected numbers of random walk starting from any vertex in the graph. We noted that time complexity of the proposed method is linear, which is quite good. Also, it is important to point out that the types of vertex play essential role in updating of PageRank.
|
|
| 3. |
- Abola, Benard, 1971-, et al.
(author)
-
Updating of PageRank in Evolving Tree graphs
- 2020
-
In: Data Analysis and Applications 3. - : John Wiley & Sons. - 9781786305343 - 9781119721871 ; , s. 35-51
-
Book chapter (peer-reviewed)abstract
- Summary Updating PageRank refers to a process of computing new PageRank values after changes have occurred in a graph. The main goal of the updating is to avoid recalculating the values from scratch. This chapter focuses on updating PageRank of an evolving tree graph when a vertex and an edge are added sequentially. It describes how to maintain level structures when a cycle is created and investigates the practical and theoretical efficiency to update PageRanks for an evolving graph with many cycles. The chapter discusses the convergence of the power method applied to stochastic complement of Google matrix when a feedback vertex set is used. It also demonstrates that the partition by feedback vertex set improves asymptotic convergence of power method in updating PageRank in a network with cyclic components.
|
|
| 4. |
- Biganda, Pitos, 1981-, et al.
(author)
-
Exploring The Relationship Between Ordinary PageRank, Lazy PageRank and Random Walk with Backstep PageRank for Different Graph Structures
- 2020
-
In: Data Analysis and Applications 3. - : John Wiley & Sons, Ltd. - 9781786305343 - 9781119721871 ; , s. 53-73
-
Book chapter (peer-reviewed)abstract
- 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.
|
|
| 5. |
- Biganda, Pitos, 1981-, et al.
(author)
-
PageRank and perturbed Markov chains
- 2019
-
In: 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. 233-247
-
Conference paper (peer-reviewed)abstract
- PageRank is a widely-used hyperlink-based algorithm to estimate the relative importance of nodes in networks [11]. Since many real world networks are large sparse networks, this makes efficient calculation of PageRank complicated. Moreover, one needs to escape from dangling effects in some cases as well as slow convergence of the transition matrix. Primitivity adjustment with a damping (perturbation) parameter ε(0,ε0] (for fixed ε0 0.15) is one of the essential procedure that is known to ensure convergence of the transition matrix [24]. If ε is large, the transition matrix looses information due to shift of information to teleportation matrix [27]. In this paper, we formulate PageRank problem as the first and second order Markov chains perturbation problem. Using numerical experiments, we compare convergence rates for the two problems for different values of ε on different graph structures and investigate the difference in ranks for the two problems.
|
|
| 6. |
- Biganda, Pitos, 1981-, et al.
(author)
-
Traditional and lazy pageranks for a line of nodes connected with complete graphs
- 2018
-
In: Stochastic Processes and Applications. - Cham : Springer. - 9783030028244 ; , s. 391-412
-
Book chapter (peer-reviewed)abstract
- 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.
|
|
| 7. |
- Silvestrov, Dmitrii, 1947-, et al.
(author)
-
Coupling and Ergodic Theorems for Markov Chains with Damping Component
- 2019
-
In: Theory of Probability and Mathematical Statistics. - 0094-9000. ; 101, s. 212-231
-
Journal article (peer-reviewed)abstract
- Perturbed Markov chains are popular models for description of information networks. Insuch models, the transition matrix P0 of an information Markov chain is usually approximated bymatrix Pε = (1-ε)P0+εD, where D is a so-called damping stochastic matrix with identical rowsand all positive elements, while ε [0; 1] is a damping (perturbation) parameter. Using procedure ofarticial regeneration for the perturbed Markov chain ηε,n with the matrix of transition probabilities Pε , and coupling methods, we get ergodic theorems, in the form of asymptotic relations for Pε,ij (n) =Pi {ηε,n =j}, as n and ε0, and explicit upper bounds for the rates of convergence in such theorems. In particular, the most dicult case of the model with singular perturbations, wherethe phase space of the unperturbed Markov chain η0,n split in several closed classes of communicativestates and possibly a class of transient states, is investigated.
|
|
| 8. |
- Silvestrov, Dmitrii, 1947-, et al.
(author)
-
Perturbation analysis for stationary distributions of markov chains with damping component
- 2020
-
In: Algebraic Structures and Applications. - Cham : Springer Nature. - 9783030418496 ; , s. 903-933
-
Book chapter (peer-reviewed)abstract
- Perturbed Markov chains are popular models for description of information networks. In such models, the transition matrix P0 of an information Markov chain is usually approximated by matrix Pε = (1 - ε) P0 + ε 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 |πε- π0 |, and asymptotic expansions for πε with respect to the perturbation parameter ε.
|
|
| 9. |
- Silvestrov, Dmitrii, 1947-, et al.
(author)
-
Perturbed Markov Chains with Damping Component
- 2021
-
In: Methodology and Computing in Applied Probability. - : Springer Science and Business Media LLC. - 1387-5841 .- 1573-7713. ; :1, s. 369-397
-
Journal article (peer-reviewed)abstract
- 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.
|
|
