Parallel two-stage algorithms for solving the PageRank problem. (November 2018)

• Record Type: Journal Article
• Authors: Migallón, Héctor; Migallón, Violeta; Penadés, José
• Is Part Of: Advances in engineering software. Volume 125(2018)
• Page Start: 188
• Page End: 199
• Publication Date: 2018-11
• Subjects: PageRank -- Parallel algorithms -- Two-stage methods -- Shared memory -- Distributed memory; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2018.03.002
• Languages: English
• ISSNs: 0965-9978

Abstract

Highlights: New parallel algorithms that use two-stage methods for solving the PageRank problem have designed. Conditions on the proposed splittings are analyzed to guarantee the global convergence. A mixed MPI/OpenMP model has been implemented. Different data distribution strategies among nodes have been considered. Numerical experiments show the competitiveness of our algorithms. Abstract: In this work we present parallel algorithms based on the use of two-stage methods for solving the PageRank problem as a linear system. Different parallel versions of these methods are explored and their convergence properties are analyzed. The parallel implementation has been developed using a mixed MPI/OpenMP model to exploit parallelism beyond a single level. In order to investigate and analyze the proposed parallel algorithms, we have used several realistic large datasets. The numerical results show that the proposed algorithms can speed up the time to converge with respect to the parallel Power algorithm and behave better than other well-known techniques.