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 for networks, graphs and Markov chains
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (MAM)ORCID-id: 0000-0002-1624-5147
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (MAM)ORCID-id: 0000-0003-4554-6528
2017 (Engelska)Ingår i: Theory of Probability and Mathematical Statistics, ISSN 0868-6904, Vol. 96, s. 61-83Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this work it is described how a partitioning of a graph into components can be used to calculate PageRank in a large network and how such a partitioning can be used to re-calculate PageRank as the network changes. Although considered problem is that of calculating PageRank, it is worth to note that the same partitioning method could be used when working with Markov chains in general or solving linear systems as long as the method used for solving a single component is chosen appropriately. An algorithm for calculating PageRank using a modified partitioning of the graph into strongly connected components is described. Moreover, the paper focuses also on the calculation of PageRank in a changing graph from two different perspectives, by considering specific types of changes in the graph and calculating the difference in rank before and after certain types of edge additions or removals between components. Moreover, some common specific types of graphs for which it is possible to find analytic expressions for PageRank are considered, and in particular the complete bipartite graph and how PageRank can be calculated for such a graph. Finally, several open directions and problems are described.

Ort, förlag, år, upplaga, sidor
2017. Vol. 96, s. 61-83
Nyckelord [en]
PageRank, random walk, Markov chain, graph, strongly connected component
Nationell ämneskategori
Sannolikhetsteori och statistik Beräkningsmatematik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
URN: urn:nbn:se:mdh:diva-36589DOI: 10.1090/tpms/1034ISI: 000412769200006Scopus ID: 2-s2.0-85055703888OAI: oai:DiVA.org:mdh-36589DiVA, id: diva2:1145921
Tillgänglig från: 2017-09-30 Skapad: 2017-09-30 Senast uppdaterad: 2019-06-25Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopusAccess to free full text

Personposter BETA

Engström, ChristopherSilvestrov, Sergei

Sök vidare i DiVA

Av författaren/redaktören
Engström, ChristopherSilvestrov, Sergei
Av organisationen
Utbildningsvetenskap och Matematik
Sannolikhetsteori och statistikBeräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 20 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