| 1. |
- Abola, Benard, et al.
(författare)
-
A Variant of Updating PageRank in Evolving Tree Graphs
- 2021
-
Ingår i: Applied Modeling Techniques and Data Analysis 1. - : John Wiley & Sons, Inc. Hoboken, NJ, USA. - 9781786306739 - 9781119821564 ; , s. 3-22
-
Bokkapitel (refereegranskat)abstract
- A PageRank update refers to the process of computing new PageRank valuesafter a change(s) (addition or removal of links/vertices) has occurred in real-lifenetworks. The purpose of updating is to avoid re-calculating the values from scratch.To efficiently carry out the update, we consider PageRank to be the expected numberof visits to a target vertex if multiple random walks are performed, starting at eachvertex once and weighing each of these walks by a weight value. Hence, it mightbe looked at as updating a non-normalized PageRank. We focus on networks of treegraphs and propose an approach to sequentially update a scaled adjacency matrix afterevery change, as well as the levels of the vertices. In this way, we can update thePageRank of affected vertices by their corresponding levels.
|
|
| 2. |
- 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.
|
|
| 3. |
- Abola, Benard, 1971-, et al.
(författare)
-
Evaluation of Stopping Criteria for Ranks in Solving Linear Systems
- 2019. - Chapter 10
-
Ingår i: 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
-
Bokkapitel (refereegranskat)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.
|
|
| 4. |
- Abola, Benard, 1971-, et al.
(författare)
-
PageRank in evolving tree graphs
- 2018
-
Ingår i: Stochastic Processes and Applications. - Cham : Springer. - 9783030028244 ; , s. 375-390
-
Bokkapitel (refereegranskat)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.
|
|
| 5. |
|
|
| 6. |
- Abola, Benard, 1971-, et al.
(författare)
-
Updating of PageRank in Evolving Tree graphs
- 2020
-
Ingår i: Data Analysis and Applications 3. - : John Wiley & Sons. - 9781786305343 - 9781119721871 ; , s. 35-51
-
Bokkapitel (refereegranskat)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.
|
|
| 7. |
- Biganda, Pitos, 1981-, et al.
(författare)
-
Exploring The Relationship Between Ordinary PageRank, Lazy PageRank and Random Walk with Backstep PageRank for Different Graph Structures
- 2020
-
Ingår i: Data Analysis and Applications 3. - : John Wiley & Sons, Ltd. - 9781786305343 - 9781119721871 ; , s. 53-73
-
Bokkapitel (refereegranskat)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.
|
|
| 8. |
- Biganda, Pitos, 1981-, et al.
(författare)
-
Modeling exchange rate volatility using APARCH models
- 2018
-
Ingår i: Journal of the Institute of Engineering. - : Nepal Journals Online (JOL). - 1810-3383. ; 14:1, s. 96-106
-
Tidskriftsartikel (refereegranskat)abstract
- ARCH (Autoregressive Conditional Heteroskedacity) and GARCH (Generalized Autoregressive Conditional Heteroskedacity) models have been used in forecasting fluctuations in exchange rates, commodities and securities and are appropriate for modeling time series in which there is non-constant variance, and in which the variance at one time period is dependent on the variance at a previous time period. In our paper we deal with APARCH models (Arithmetic Power Autoregressive Conditional Heteroskedasticity) in order to fit into a data series with asymmetric characteristics. We use Kenyan, Tanzanian and Mozambican data and perform the time series analysis and obtain a model that characterize the data set under consideration. Journal of the Institute of Engineering, 2018, 14(1): 96-106
|
|
| 9. |
- Biganda, Pitos, 1981-, et al.
(författare)
-
PageRank and perturbed Markov chains
- 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. 233-247
-
Konferensbidrag (refereegranskat)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.
|
|
| 10. |
- Biganda, Pitos, 1981-, et al.
(författare)
-
PageRank and Perturbed Markov Chains
- 2021
-
Ingår i: Applied Modeling Techniques and Data Analysis 1. - : John Wiley & Sons, Inc. Hoboken, NJ, USA. - 9781786306739 - 9781119821564 ; , s. 57-74
-
Bokkapitel (refereegranskat)abstract
- PageRank is a widely used hyperlink-based algorithm for estimating the relative importance of nodes in networks. Since many real-world networks are large sparse networks, efficient calculation of PageRank is complicated. Moreover, we need to overcome dangling effects in some cases as well as slow convergence of the transition matrix. Primitivity adjustment with a damping (perturbation) parameter is one of the essential procedures known to ensure convergence of the transition matrix. If the perturbation parameter is not small enough, the transition matrix loses information due to the shift of information to the teleportation matrix. We formulate the PageRank problem as a first- and second-order Markov chains perturbation problem. Using numerical experiments, we compare convergence rates for different values of perturbation parameter on different graph structures and investigate the difference in ranks for the two problems.
|
|
