mdh.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 for networks, graphs and Markov chains
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (MAM)ORCID iD: 0000-0002-1624-5147
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (MAM)ORCID iD: 0000-0003-4554-6528
2017 (English)In: Theory of Probability and Mathematical Statistics, ISSN 0868-6904, Vol. 96, 61-83 p.Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
2017. Vol. 96, 61-83 p.
Keyword [en]
PageRank, random walk, Markov chain, graph, strongly connected component
National Category
Probability Theory and Statistics Computational Mathematics
Research subject
Mathematics/Applied Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-36589OAI: oai:DiVA.org:mdh-36589DiVA: diva2:1145921
Available from: 2017-09-30 Created: 2017-09-30 Last updated: 2017-10-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Access to free full text

Search in DiVA

By author/editor
Engström, ChristopherSilvestrov, Sergei
By organisation
Educational Sciences and Mathematics
Probability Theory and StatisticsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

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