https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
PageRank in evolving tree graphs
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. Department of Mathematics, School of Physical Sciences, Makerere University, Kampala, Uganda. (MAM)
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. Department of Mathematics, College of Natural and Applied Sciences, University of Dar es Salaam,Tanzania. (MAM)ORCID iD: 0000-0001-7822-2103
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (MAM)ORCID iD: 0000-0002-1624-5147
Department of Mathematics, School of Physical Sciences, Makerere University, Kampala, Uganda.
Show others and affiliations
2018 (English)In: Stochastic Processes and Applications: SPAS2017, Västerås and Stockholm, Sweden, October 4-6, 2017 / [ed] Sergei Silvestrov, Anatoliy Malyarenko, Milica Rančić, Springer, 2018, Vol. 271, p. 375-390Chapter in book (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2018. Vol. 271, p. 375-390
Series
Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009 ; 271
Keywords [en]
Breadth-first search, Forward edge, PageRank, Random walk, Tree, Forestry, Graph theory, Iterative methods, Random processes, Stochastic systems, Trees (mathematics)
National Category
Computational Mathematics Probability Theory and Statistics
Research subject
Mathematics/Applied Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-41833DOI: 10.1007/978-3-030-02825-1_16ISI: 000674508200015Scopus ID: 2-s2.0-85058567338ISBN: 978-3-030-02824-4 (print)OAI: oai:DiVA.org:mdh-41833DiVA, id: diva2:1274027
Conference
International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789
Funder
Sida - Swedish International Development Cooperation AgencyAvailable from: 2018-12-27 Created: 2018-12-27 Last updated: 2021-11-03Bibliographically approved
In thesis
1. Perturbed Markov Chains with Damping Component and Information Networks
Open this publication in new window or tab >>Perturbed Markov Chains with Damping Component and Information Networks
2020 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2020
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 326
National Category
Mathematics
Research subject
Mathematics/Applied Mathematics
Identifiers
urn:nbn:se:mdh:diva-51550 (URN)978-91-7485-485-5 (ISBN)
Public defence
2020-12-10, Lambda +(Online Zoom), Mälardalens högskola, Västerås, 15:15 (English)
Opponent
Supervisors
Available from: 2020-10-19 Created: 2020-10-15 Last updated: 2020-11-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Abola, BenardBiganda, PitosEngström, ChristopherSilvestrov, Sergei

Search in DiVA

By author/editor
Abola, BenardBiganda, PitosEngström, ChristopherSilvestrov, Sergei
By organisation
Educational Sciences and Mathematics
Computational MathematicsProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1308 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf