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
Graph partitioning and a component wise PageRank algorithm
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (Matematik/tillämpad Matematik)ORCID iD: 0000-0002-1624-5147
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (Matematik/tillämpad Matematik)
(English)Manuscript (preprint) (Other academic)
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.

Keyword [en]
PageRank
National Category
Computational Mathematics
Research subject
Mathematics/Applied Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-33455OAI: oai:DiVA.org:mdh-33455DiVA: diva2:1039450
Note

Submitted to Journal.

Available from: 2016-10-24 Created: 2016-10-24 Last updated: 2016-12-14Bibliographically approved

Open Access in DiVA

No full text

Other links

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

Search in DiVA

By author/editor
Engström, ChristopherSilvestrov, Sergei
By organisation
Educational Sciences and Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 16 hits
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