mdh.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
PageRank in evolving tree graphs
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. Department of Mathematics, School of Physical Sciences, Makerere University, Kampala, Uganda. (MAM)
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. Department of Mathematics, College of Natural and Applied Sciences, University of Dar es Salaam,Tanzania. (MAM)
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (MAM)ORCID-id: 0000-0002-1624-5147
Department of Mathematics, School of Physical Sciences, Makerere University, Kampala, Uganda.
Visa övriga samt affilieringar
2018 (Engelska)Ingår i: 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, s. 375-390Kapitel i bok, del av antologi (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Springer, 2018. Vol. 271, s. 375-390
Serie
Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009 ; 271
Nyckelord [en]
Breadth-first search, Forward edge, PageRank, Random walk, Tree, Forestry, Graph theory, Iterative methods, Random processes, Stochastic systems, Trees (mathematics)
Nationell ämneskategori
Beräkningsmatematik Sannolikhetsteori och statistik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
URN: urn:nbn:se:mdh:diva-41833DOI: 10.1007/978-3-030-02825-1_16Scopus ID: 2-s2.0-85058567338ISBN: 978-3-030-02824-4 (tryckt)OAI: oai:DiVA.org:mdh-41833DiVA, id: diva2:1274027
Konferens
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
Tillgänglig från: 2018-12-27 Skapad: 2018-12-27 Senast uppdaterad: 2018-12-31Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Abola, BenardBiganda, PitosEngström, ChristopherSilvestrov, Sergei

Sök vidare i DiVA

Av författaren/redaktören
Abola, BenardBiganda, PitosEngström, ChristopherSilvestrov, Sergei
Av organisationen
Utbildningsvetenskap och Matematik
BeräkningsmatematikSannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 432 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf