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
A Variant of Updating Page Rank in Evolving Tree graphs
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (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, Makerere University, Kampala, Uganda. (MAM)
Show others and affiliations
2019 (English)In: Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019 / [ed] Christos H. Skiadas, ISAST: International Society for the Advancement of Science and Technology , 2019, p. 31-49Conference paper, Published paper (Refereed)
Abstract [en]

PageRank update refers to the process of computing new PageRank values after change(s) (addition or removal of links/vertices) has occurred in real life networks. The purpose of the updating is to avoid recalculating the values from scratch. To efficiently carry out the update, we consider PageRank as the expected number of visits to target vertex if multiple random walks are performed, starting at each vertex once and weighing each of these walks by a weight value. Hence, it might be looked at as updating non-normalised PageRank. In the proposed approach, a scaled adjacency matrix is sequentially updated after every change and the levels of the vertices being updated as well. This enables sets of internal and sink vertices dependent on their roots or parents, thus vector-vector product can be performed sequentially since there are no infinite steps from one vertex to the other.

Place, publisher, year, edition, pages
ISAST: International Society for the Advancement of Science and Technology , 2019. p. 31-49
Keywords [en]
PageRank, randomwalk, graph, networks.
National Category
Probability Theory and Statistics Computational Mathematics
Research subject
Mathematics/Applied Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-47083ISBN: 978-618-5180-33-1 (electronic)OAI: oai:DiVA.org:mdh-47083DiVA, id: diva2:1394753
Conference
ASMDA2019, 18th Applied Stochastic Models and Data Analysis International Conference
Funder
Sida - Swedish International Development Cooperation AgencyAvailable from: 2020-02-20 Created: 2020-02-20 Last updated: 2021-01-08Bibliographically 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

http://www.asmda.es/

Authority records

Abola, BenardBiganda, PitosEngström, ChristopherAnguzu, CollinsSilvestrov, Sergei

Search in DiVA

By author/editor
Abola, BenardBiganda, PitosEngström, ChristopherAnguzu, CollinsSilvestrov, Sergei
By organisation
Educational Sciences and Mathematics
Probability Theory and StatisticsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 917 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