Perturbed Markov Chains with Damping Component and Information Networks

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Search: onr:"swepub:oai:DiVA.org:mdh-51550" > Perturbed Markov Ch...

1 of 1
Previous record
Next record
To hitlist

Perturbed Markov Chains with Damping Component and Information Networks

Abola, Benard (author): Mälardalens högskola,Utbildningsvetenskap och Matematik,MAM

Silvestrov, Sergei, Professor, 1970- (thesis advisor): Mälardalens högskola,Utbildningsvetenskap och Matematik

Engström, Christopher, 1987- (thesis advisor): Mälardalens högskola,Utbildningsvetenskap och Matematik

Silvestrov, Dmitrii, 1947- (thesis advisor): Mälardalens högskola,Utbildningsvetenskap och Matematik

Malyarenko, Anatoliy, 1957- (thesis advisor): Mälardalens högskola,Utbildningsvetenskap och Matematik

Rancic, Milica, 1977- (thesis advisor): Mälardalens högskola,Utbildningsvetenskap och Matematik

Anisimov, Vladimir, Professor (opponent): Center for Design and Analysis, Amgen Inc.

show less...

(creator_code:org_t)

ISBN 9789174854855
Västerås : Mälardalen University, 2020
English.
Series: Mälardalen University Press Dissertations, 1651-4238 ; 326

Related links:: https://mdh.diva-por... (primary) (Raw object); show more...; https://urn.kb.se/re...; show less...

Doctoral thesis (other academic/artistic)

Abstract Subject headings

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.

Subject headings

NATURVETENSKAP -- Matematik (hsv//swe)
NATURAL SCIENCES -- Mathematics (hsv//eng)

Keyword

Mathematics/Applied Mathematics
matematik/tillämpad matematik

Publication and Content Type

vet (subject category)
dok (subject category)

Find in a library

Perturbed Markov Chains with Damping Component and Information Networks (Search the publication in LIBRIS)

To the university's database

1 of 1
Previous record
Next record
To hitlist

Find more in SwePub

By the author/editor: Abola, Benard; Silvestrov, Serg ...; Engström, Christ ...; Silvestrov, Dmit ...; Malyarenko, Anat ...; Rancic, Milica, ...; show more...; Anisimov, Vladim ...; show less...

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics

Parts in the series: Mälardalen Unive ...

By the university: Mälardalen University

Search outside SwePub

Extend your search to:: Google; Google Book Search; Google Scholar

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

LIBRIS.kb.se