mdh.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Graph partitioning and a component wise PageRank algorithm
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (Matematik/tillämpad Matematik)ORCID-id: 0000-0002-1624-5147
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (Matematik/tillämpad Matematik)
(engelsk)Manuskript (preprint) (Annet vitenskapelig)
Abstract [en]

In this article we will present a graph partitioning algorithm which partitions a graphinto two different types of components: the well known ‘strongly connected components’ as well as another type of components we call ‘connected acyclic component’. We will give analgorithm based on Tarjan’s algorithm for finding strongly connected components used to find such a partitioning. We will also show that the partitioning given by the algorithm is unique and that the underlying graph can be represented as a directed acyclic graph (similar to a pure strongly connected component partitioning). In the second part we will show how such an partitioning of a graph can be used to calculate PageRank of a graph effectively by calculating PageRank for different componentson the same ‘level’ in parallel as well as allowing for the use of different types of PageRankalgorithms for different types of components. To evaluate the method we have calculated PageRank on four large example graphs and compared it with a basic approach, as well as our algorithm in a serial as well as parallel implementation.

Emneord [en]
PageRank
HSV kategori
Forskningsprogram
matematik/tillämpad matematik
Identifikatorer
URN: urn:nbn:se:mdh:diva-33455OAI: oai:DiVA.org:mdh-33455DiVA, id: diva2:1039450
Merknad

Submitted to Journal.

Tilgjengelig fra: 2016-10-24 Laget: 2016-10-24 Sist oppdatert: 2016-12-14bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

https://arxiv.org/pdf/1609.09068.pdf

Søk i DiVA

Av forfatter/redaktør
Engström, ChristopherSilvestrov, Sergei
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 50 treff
RefereraExporteraLink to record
Permanent link

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